I found this quite easy. The tools worked great. I agree with Andy, if you push the tool into the groove, then lift or pry it up so the tip of the tool is down inside the back cover, you should be able to slide it across to pop the clips quite easily. Once you get the first two sides open, it goes quick.
I also did this without having to remove the Torx screw. It helped to lift the battery up a bit to give the wires a little slack, and then just feed them around the corner of the motherboard. Putting the new battery in, I just fed the wires around the corner, and used the opening tool to push them the final bit of the way around the corner.
My old iPod is like new now! Hours and hours of battery life, when it would previously die after 5 minutes.