Separate sidebar content based on category / tag

Hi there – i’m currently running an entertainment website using categories (videos, music, photos, interviews) and tags for artists’ names. That’s working fine, however, I would like to show related items in the sidebar. I.e. on any article about Madonna, I would like to show:
– 5 ‘image’ posts by Madonna
– 5 ‘video’ posts by Madonna
– 5 ‘interview’ posts by Madonna
– 5 ‘music’ posts by Madonna
– Madonna on Twitter (using a default Twitter widget but somewhere you would have to specify her twitter handle)

YARPP or other related item plugins probably don’t do the trick.

I have a feeling using tags isn’t right, as a lot of posts will have been tagged with multiple artists (i.e. a post about Madonna’s album Hard Candy, would also be tagged by Timbaland the producer, and obviously I wouldn’t want to show articles solely about him in the side view).

I’m essentially after something where you can specify what the main topic is of that post (rather than tag based), and based on that it would pull the correct sidebar together. The website below does a similar job (but doesn’t run WordPress):
http://www.contactmusic.com/news.nsf/story/rihanna-tweets-britney-after-remix-release_1212037

Any idea how I might be able to get the same results on WordPress (are there themes out there that already do this?) Should I be using custom taxonomies and if so, how should I set this up?