Well, if you haven't installed any other shields, then part of your connections are not so protected (network shield not installed).
Are you having any kind of hardware connected during your boots or shut downs? I mean, any card reader, USB device, special modem, wi-fi...
At least, just for testing, you should try disconnecting (or powering off) any "optional" hardware component.
Please report back.