Time Machine: disk was not ejected properly
This happens because of a USB Sleep issue with some external usb devices. This happens when the USB disk is put on sleep.

Some people claim that this problem is solved by disabling Put the hard disk(s) to sleep when possible in the Energy Saver preferences pane.