I would not have thought that there would be performance issues with multiple primary keys. This is more or less equivalent to having multiple indexes (when inserting, you spend a little more time calculating the index values).
Sometimes a data model makes more sense with multiple keys. I would take care to be the first and worry about performance secondly. You can always add more indexes, improve your queries or change server settings.
I think that most of all I came across a 4-column primary key. Makes me cringe a little, but it worked & sup1 ;.
[1] “worked” is defined as “an application executed for specification” and does not imply that actual tasks were performed using the application. :)