Apart from checking the battery's the right way up, have a look that the contacts are all correct. When I changed the battery the first time, my key didn't then work. It turned out I'd bent a contact to the battery, (very easy to do), and bending it very gently back into place solved the problem.

 

If you can get into the car try docking it into the slot under the steering wheel