Why does Time Machine only backup after a reboot?
Things to check:


Software Update (read the description to see if it fixes the issue
for your OS X 10.7 server)
Check if OS X 10.7 Server requires its Time Machine to be formatted
using Case-sensitive, Journaled Mac OS X Extended. Anecdotally,
I've always formatted my Time Machine backup as  Mac OS X
(Journaled) and Time Machines works fine.
Check the Permissions. Check that your OS X 10.7 Server user id has access to the USB partition.