Version:            (using KDE KDE 3.5.2)
Installed from:    Ubuntu Packages

This can somehow be considered as a bug, too. The problem appears whenever you got the cue file that doesn't match the filename of the mp3 file it's meant to be used with. Amarok, in such situation, won't 'see' this cue file at all, and make use of it. Usually, such situation happens for a "scene releases", where files are named like 00-(...).cue and 01-(...).mp3 etc. The solution is to for Amarok to take a look inside the cue file and see if the FILE field is present and if so, to check if the file it indicates exist in the current subdirectory. If it does, Amarok can use it just like it does now.