So I took the Macbook into the Genius Bar Saturday. Before even finishing explaining my problem, the tech knew what the issue was. He said there are 5-10 Macbooks a day coming in with the same issue. He went and grabbed me a new battery from the Retail side of the store. He put it into the Macbook and it was fixed. He took the battery from my Macbook and marked it defective and put it in the new box, eventhough Apple's policy is that I have to wait for a battery to be ordered for me.
His recommendation to me was to not let my Macbook discharge all the way in the future, Apple clearly has an issue with the PMU getting enough power to a dead battery to bring it back to life.
Good luck to anyone else with this same issue.
Thanks to the Genius bar for having common sense and fixing my Macbook right there on the spot.
I don't know about you guys but I intend to keep doing this until they decide to fix the problem. If I have to get a new battery every month, fine by me. Its apple's money down the tubes.