I think it will be still be a long time before robots replace humans, even at Wal-Mart-like jobs. There are a few places where it's appropriate (self checkout, for instance), but there are things that humans do without batting an eyes are very very hard or expensive for robots (spoken communications, visual and auditory classification, spatial navigation and obstacle negotiation).
Humans aren't really that expensive honestly. Considering that the rent on a few servers from EC2 can equal the hourly wage of a Wal-Mart employee, it's going to be a while before these equations start working out.
You're absolutely right about people not being very expensive though. Labor costs actually make manual manufacturing in China less expensive than in fully roboticized factories in Japan or the USA for many things.
It's pretty fucking hard to automate programming. Heck, we can't even solve voice and character recognition.