This is possibly because you had a menu assigned, then you changed themes, and now there is no longer a menu assigned. Because WordPress generates slightly different html for an assigned menu than for an autogenerated menu, this is likely why you have the issue.
For example, on a theme of mine Im developing, if I changed them and back the menu was pushed down 20 pixels, which was gone when I assigned my header menu, some tweaked CSS rules corrected the issue.