Hopefully someone else will flesh out this answer, I don’t have the time to write out a full solution right now…
If you’re using WordPress 3.1, look at the tax_query parameter that you can pass to query_posts. It can handle multiple taxonomies and relationships between them.
Otto’s post WordPress 3.1: Advanced Taxonomy Queries is the best explanation I’ve seen of what tax queries can do, and how to use them…
In older versions of WP, you’re stuck using a plugin like this one, or rolling your own fairly complex SQL queries.