Odd, that's how it works for me. But I always did this after adding contacts, not after deleting, that's the only thing I can think of.

EDIT:
I think you can delete and re-add your facebook account in the accounts manager, that should do the trick. I don't know if by doing so you'd lose your chat history though.