Half of my outlet stopped working?

you can get the same economy of wire using the same leg.

the wiring in the wall doesn’t have to change, you can relocate the wire in the fuse/breaker box to put both circuits on the same leg if this hazard exists (should only be done by someone skilled in electrical work).

+1.

This is the most likely cause. I’ve done an enormous amount of electrical work in my house and have had a few outlets that have had this problem.

http://www.smarthome.com/images/22490b1side2big.jpg

In this picture, you can see the little gold bar that connects the two outlets. If this bar breaks, the outlets need to be wired separately to work.

That was the bar I was meaning. Thanks for the picture.