What version are you on? If you haven't opened a high priority support case yet, this sounds like the perfect opportunity to do this. So a tsm restart doesn't restart properly? You may want to do the following:
1. Try to do a validate resources. tsm maintenance
2. There's a verify of the database integrity command somewhere, I'm not finding it right now, but when I do I will respond.