I get the same phenomenon restarting, but when it finishes the start-up the TM icon becomes the standard green with TM logo (as apparently the last step in the start-up process).
It would seem that your set-up isn't running to 'completion' upon restart but fixes itself once scheduled backups resume.
What happens if instead of restart you shut down for 5-10 minutes and then start up?
Before you try that, try force quitting (relaunching) Finder (via the Command-Option-Escape window).
One of those suggestions might fix the problem but won't explain it.
