Before you do anything, make sure you Log OFF from Facebook on your Facebook for Android App. And also delete your Facebook Account from your Phone.
You can try deleting your Facebook App and reinstalling it from the market if you think is necessary, even if it doesn't come with the Sync all existing Contacts feature this steps should work.
I have no idea why it does not work with 3G, but WI-FI was the answer for me.
I know all the screenshots say 3G, thats because I already synced all my Facebook friends and I don't have Wi-Fi at my house.
Good Luck~!