From what I can understand, you are running into the restrictions that the 2.0 API places around interacting with users who have not run your app and given it any permissions.
This is a radical departure from 1.0 where the user of your app could allow your app access to data about their friends. In the new API, the friend must have used your app and granted permissions for your app to see their data.
One of the ways that Facebook is implementing this is that user ID numbers are app specific in 2.0. i.e. If you happen to know someone's Facebook user ID, perhaps from a 1.0 based app, it is not usable by your app. There is no way to ask for a complete list of a user's friends anymore, although there are some API calls to do things like tag photos with friends or invite friends that have not used your app - but this still doesn't give you access to their profiles. The IDs these APIs give you can't be used that way.
The changes are described here: Upgrading to 2.0 User IDs
If these seem pretty restrictive to you, you're not alone. Thank the spammers out there.