There are few possible reasons.... Make sure the root partition isn't running out of space, make sure the file is not "world-writable" i.e. rw-rw-rw /etc/utmp. I've heard of solutions when you "zero" the files, reboot and hope to work, although I haven't done it myself.
What actions have been done prior to system reboot ? Hardware maintanence, abnormal interruption of "shutdown -r" || reboot ?
Did you try grepping for erros at the log files, and also, what is the OS ?