You should have used a
bridge camera rather than your 5DII. They are after all specifically designed for this kind of photography.

Seriously though, it really looks like motion blur to me. As to what caused it, it could be one thing, or a combination of things.
I can't find the link but someone did a vibration test on a range of tripods and it's surprising just how long a little vibration from touching the camera, or from a breeze, or from the mirror itself can take to damp down, even with a really expensive well respected tripod & head.
I've now come round to always shooting from live view when doing a landscape, with silent shutter mode 1. I frame the shot through the vf, slip into live view, give it at least ten secs for residual vibration to damp down, then take the shot with my cable release. This procedure doesn't protect me from the effects of a breeze, but it has got me sharper shots.
But I would also agree with comments about the shutter speed. The sub 1/60 - 1 sec range leaves you really vulnerable to any movement. Longer is OK. Shorter is OK. But 1/40 is still living on the edge.