I would make sure the replacement battery is in correctly, and that it is OK. Maybe test it with a multimeter or have Radio Shack test it or an auto supply store possibly.
Also try holding the silver end of the fob directly above the pushbutton and starting it that way. It is supposed to work like that when the battery is dead. If it starts, you know it is still programmed.
Is it unlocking the doors remotely? If none of this works, your next step would be the dealer.
EDIT-It may be the end that isn't silver that you need to hold up to the pushbutton.
2010 SLS FWD CVT-Azure Grey