If I were you I would be paranoid and run a disk check for bad sectors. I'm not totally sure but if my block database started acting funky I'd be concerned.
I'd also question how old the hard drive is OP in your machine, can you also try defragmenting it as well as what RGB suggests?
Description of Problem: Every time I start bitcoin-qt I get a "Rewinding blocks" message that lasts for hours before start syncing again.
It used to be fine but some weeks ago it started behaving this way.
After letting it rewind, everything is fine until I shut it down.
When you shut it down, do you wait for the window to close before shutting down. E.G, do you do a forceful shutdown or do you allow it to shut down on it's own before turning off your computer.
The debug.log as achow says will be very helpful here, it'll be in the ~/.Bitcoin folder (if you use default settings).