Welcome to Allpar. There are a few things that will disable a remote start for safety and tamper reasons. See p. 24-25 of your owners manual. As mentioned, fault codes may prevent a remote start.
If this just stopped working after a fob battery change, it may be that the code has been 'corrupted' and it may need a module reset or dealer assistance to get the feature back?