You said you didn't mess around with any of the settings, just checked 'use depth map shadows'??
Try increasing the dmap resoloution of the light which is casting shadows. When this is too low, it can cause shadows too look jagged or wierd. Try setting it to the same as your rendering resoloution, then increasing it to get the look you want. Be careful on setting it too high though, as it can kill your render times.
Hope this helps