Don't feel dumb - cripes, I'm a pretty bright guy (in some ways). The first time I took that tire off, I slammed the whole back end around (just following the instructions in my manual). I finally got the danged thing off, but only after removing those little lead-ish shims at the ends of the wheel adjusters. I scratched the back wheel for good measure, forcing the chain over it. Then I figured out the axle trick.
My excuse is that the manual certainly, strongly implied that this simply sliding the wheel forward method would work.
It was probably the same manual that said to rough up the shoes a bit with sandpaper - just enough to take the shine off. I did that, and the brakes worked terrifically immediately I reinstalled the wheel and connected everything.
Good on you for changing them - the best part for me was getting to start over on the rear brake adjustment nut.