After messing around with the settings, I think I isolated the problem (at least in my case).
Go to Settings -> Sound. If you have "Silent mode" checked and the "Vibrate" option set to "Only in silent mode", but your phone isn't vibrating for an incoming SMS messages, then the problem may be your "Notification volume" setting.
To fix this, go to Settings -> Sound and temporarily uncheck "Silent mode". Go to the "Volume" submenu. The last setting slider, "Notification volume", is probably turned all the way down. Move the slider to the right. The further right you move it, the more intense the vibration will be. After doing this, press "OK". Re-check the "Silent mode" option. That should fix the problem.
Personally, I think that having the the volume setting control the vibration (or lack thereof) is not very intuitive. I was just about to set up Handcent as a replacement SMS app before I figured out this fix. Hope it helps someone else.