I got no problems here myself. The contact that you are trying to contact (!), does he/she have a name in an Italic font or normal?
If it is Italic font, chances are you still have to do a Roster/Subscribe and a Roster/Accept Subscription from the menu.
Hope this helps,
Gerb