i don't know if it will help you but ...
first i think you should use 3 tables like this:
bands(band_id, band_name)
users(user_id, nick)
fav_band(user_id, band_id)
then you have to generate a string with the id's of the favourite bands of the $given_user_id separated by comma looking like this:
'band_id1, band_id2, ...' (lets call it $band_string)
SELECT f.user_id, u.nick, count(f.user_id) count_of_matches
FROM fav_band f INNER JOIN users u ON f.user_id=u.user_id
WHERE f.band_id IN ($band_string) AND f.user_id<>$given_user_id
GROUP BY f.user_id
ORDER BY count_of_matches DESC
i think there's no need to explain how to get the percentage?!