If I remember correctly, from the manufacturer, 500 GB should work. I had a WD 320 GB in it.
Total time about an hour and a half, to remove and put it back together. And I knew what I was doing as this is the second time I did this. Shame on Asus for subjecting people to this monstrosity. The only thing that pretty much didn't need to be removed is the motherboard. The intent from manufacturers, like Asus, was clear: don't bother with upgrading/replacing, just buy a new netbook.
A couple of points: I would change the sequence of steps, from Step 2 go to Step 6-7-8, THEN to Step 3-4-5, so you don't have a loose fumbling keyboard to deal with.
Also, yes, on mine too, only one screw securing the hard drive tray to motherboard, the other one is missing. It never made a difference.
Removing the upper case is tricky. Pry it open with the smallest plastic tool or screwdriver you can find, at the top near the hinges, and insert a small plastic card (ie a supermarket/drugstore key card) working your way down and around.
Having blasted Asus though, one comment is in order, the craftsmanship is very good.