Android Market auto restore apps not working
Did you look in your "Library"? 

I recently did a factory reset and I can see all of the apps that I'd previously had installed, not just the ones I've only just gotten around to.