If the issue persists, try re-pairing the remote with the Fire Stick as the connection might have been lost during battery replacement.