Given that background, I can believe it. Before I learned how to lift from Starting Strength, when I was at my fattest and most sedentary, I decided to get off my ass and walk a mile 4 times a week. It made my legs bigger.
As Rip said, it's the novice effect -- when your muscle development is low enough, pretty much anything you do, any increase in activity, will make you bigger and stronger. Even low-intensity running will do it because a novice's body is just that eager to grow muscle. And you said you were eating well, too, so it all fits together and makes sense.