Did you have a service center or mobile service person change the battery? If so, I suggest having them fix the problem.
Did you change the battery yourself? A couple of easy things to check...first see if the replacement battery is actually good (remove from the fob and check with a voltmeter). If it's dead, then there's your problem. I've had a new fob fail after a week with a dead battery.
Another thing to check is to be sure you didn't damage the battery contacts when you removed the old battery. They are somewhat fragile compared to the amount of force that's sometimes needed to get the battery out. I've done that too.
Good luck!
Bruce.