If that doesn't work, Select profiles from the home screen, scroll to advanced, press the track ball. From there highlight your vibrate profile, press the menu key and select edit. Scroll down to phone and verify it is set to vibrate.
Do you get any ringtones at all. Is it only the vibrate function not working. If you change your profile to Vibrate & Ring, does it vibrate before the ring?