Ok, status update: I pulled the PS so I could get at the motherboard battery. It was still a struggle, but I got it out. I went to Circuit City and had the Joe grab a new one. Got home, put it in... it was too thin and the little clip did not press it down properly
So I will go back tomorrow and ask for a "thicker" one. Alas.