I had this same very issue...
When adding new contacts to my phone, I would go out and try to link them to their Facebook page only to not be able to find them in the Facebook list.
If I go to Facebook on my phone, they are all there.... But not when I try and link to them via People (contacts)...
First I thought it was the phone... Then the facebook security settings, etc.....
Well.... come to find out.... I had changed my password a few months ago... and apparently, that's when Facebook for HTC Sense stopped syncing. Of course you don't get any error... and you won't know you are not syncing until you try and link a contact to a new facebook friend with a contact... and of course, the normal facebook on my phone works fine and updates... so again, because you aren't getting a sync error, you never know unless you notice.
The way I fixed this was to remove the Facebook for HTC Sense from the Account area. Then I re-added it and put in the correct info. Then I hit sync and went to the people list... All the facebook photos were gone and started to re-populate.
It took a while, but I went in to find a person that was missing before and they were there this time.... so, that's what fixed it for me.... a simple password change and it whacked me...
Hope this helps!
Lego