I rode into df last November, and I definitely would not do it again. The traffic, and the crazy cabbies just aren't worth the headache. And I had to park my bike on the street, which I wasn't happy about. I came back a couple days later to check on it, and somebody had picked it up (500 lb bike) and moved it on to the sidewalk so that they could park there. A pretty good effort since the tires were chained up.
A couple years ago when I went through df with a van, we just found a place outside the city by a metro line, and left our van in a parking garage. We just saw a sign that said "Parking", and the family charged a reasonable rate. The sketchy part was the metro, where my friend got pick pocketed. Watch for people crowding you as you get on the train or bus.

As for other places: Hostel Luz de Luna, in Oaxaca has space to park a bike, and the Hotel Casa del Callejon in Puebla is right near the main square, and the guy will let you park your bike there. If you have a Lonely Planet guide, it's the same place that's listed as the Hostel Santa Maria (new owner). The guy is really friendly, so I'd imagine he'd be more than happy to let you keep your bike in the courtyard for a bit. He speaks pretty good english as well.

I probably passed you on the road, because I just came from Oaxaca through to Guadalajara in the last couple days.