I tried rigging a character with automatic weights and did, but it deformed the mesh severely, I did remove doubles, recalculating normals, etc, but nothing worked. Any ideas for what the cause of the problem might be?
That is the IK-Chain's doing. If you switch from Pose Position to Rest Position, you can tell, that your mesh is still ok.
This is however a very easy fix: All you need to do is adjust the roll of the bone that has the IK-Constraint on it. You do by selecting the bone in Pose Mode and the going to the Properties Window and Bone Constraints Tab.