Open Handcent and go to Menu > Settings (or click on the wrench in the top right)
Scroll down to Notification Settings and click
About halfway down the screen is the vibrate settings.
Note: You can customize these for different people. Repeat the above, but go into a conversation first, before you go into settings. You will then be setting notifications (led, sound, vibrate, vibrate pattern) for only that contact.
Is the master vibrate turned on for your phone? This will also turn it on for calls, but it's the only thing I can think of that might be it. Settings > Sound and Display
It is on for me, and the vibrate works on my notifications. I also have my notification sound set to the default (Droid) and not silent. That could be it too.
