For a long time, I have been unsatisfied with the fact that you can only assign one single genre for each song / album / whatever. Usability would profit a lot if you could define more than one. Think about it: you could make much better definitions for bands, like "Spahn Ranch is Electronic, from America, has a Male Voice" and so forth, so you could filter by Male Voice, then successively select more criteria so you get a nice selection of what you are in the mood for right then.
It would especially be great for bands who can not be associated with a single genre; you could also make a filter that goes "Give me bands with similar genres as Spahn Ranch".

You may wish to look into labels, which have been introduced in Amarok 1.4.5. These are similar to last.fm tags, and allow you to extend your music tagging. Support is only rudimentary at the moment (and will probably stay that way for the 1.4 series) but you can create smart playlists and order your collection with these labels. Have a play - I think you'll find you can do a lot of what you want with them.

According to Wikipedia (not the most of reliable source ok) A Frame (eg title, genre) may contain multiple values in ID3 V2.3 this value is '/' in ID3 V2.4 'null character' is used instead. Not sure about other container formats.

It would be cool if either of those were implemented in Amarok to store multiple values.

Checked out Vorbis Comments - also from Wikipedia...

"Field names are also permitted to be used more than once. It is encouraged to use this feature to support multiple values, for example two artist=... fields to list both artists of a single composition."

APE V2 also supports this though in a slightly different way.

"APEv2 also differs from Vorbis comment in the way lists of values are handled. Suppose a certain song has two artists. In Vorbis comment this will result in two ARTIST entries, but in APEv2 this will result in one Artist field with the two artists separated by a null character (a byte with the value zero)." -- from hydrogen audio

That leaves WMA and MP4/AAC in the list of commonly used tagging formats.

The next step is making sure that Taglib supports this....
I would dearly like to see amarok support multiple artists and genres at the very least

Ok Taglib seems to support multiple Tags.... At least for IDv2 and Ogg (please correct me if I am wrong here)...
But not in the Abstract interface.(which is a bit of a problem as that would mean either adding convenience functions to libtag or dealing with ogg and mp3/ape differently)

On the amarok side for editing my suggestion would be to use a non printing character as a separator between multiple values for a tag "null" if it is not going to cause too many complications and display that character with it mapped to something like "CTRL" + "Spacebar"...
Alternatively tags contained in either ( ), [ ], { }, < > (which ever works best) could interpret a comma "," as the seperator for multiple values.

A file with multilple tags should be accessible through each tag...