I had this problem too, nothing worked. Toggled native messenger app vibrate on/off, tried Handcent long/short/custom, etc. Nothing worked, phone vibrated for calls, but not messages.
Read on howardforums to try the app "Sound Manager," use "vibrate settings" toggled "vibrate whenever possible," and it worked.
Handcent & native messaging vibrate upon receive message and can set custom length vibrate alerts in Hancent. App is in the market for free, good luck.