UPDATE: After searching around I noticed other people were having this same problem so maybe this will help.
I ordered a new battery from Rapid Repair and set to work changing it. Getting the Zune open was extremely difficult and the shiny plastic covering the screws put up one heck of a fight. It took a delicate balance of force and finesse to get it open without breaking anything. But once it was apart the soldering was very easy. I was worried that since it's a pretty small device the area in which I would have to work would be quite cramped but that wasn't the case. I tacked on the 4 wires, snapped the Zune back together, and bingo! She's working like new, and for a lot less than sending it in for a repair.
Difficulty of repair: 4 out of 5
Time: about an hour