I'm not familiar with Kubuntu, what Qt style do they use?
It does not look like standard Fusion style, so maybe they use a buggy custom Qt style.
Try setting the style in appearance settings to fusion.
@jonas It sounds like you are saying that the default settings of; Save album covers in album directory and use hash is broken in the case where files are not physically stored in album specific folders. If this is the case, then why bother to use a hash at all? I would have expected that whether using a hash or a pattern, whether stored in the album's (or more accurately file's) directory or located in a hidden directory in the user's home folder, that there is some database that associates a particular physical image file with a particular physical music file.
To do otherwise creates a hidden trap for any user that may choose to store their music files in any structure other than limiting folders to only containing the files of a single album. If someone were to put all of their Goo Goo Dolls files in a folder, or all their songs from the 80's, or as I have done with some of my folders, just collections of completely unrelated music files then Strawberry's current implementation is unable to correctly handle the situation.