Some suggest to insert the new battery upside down for a moment instead of waiting 30 seconds, but I never tried it this way.
I know I am way late to the game hear but if you still have your old Garmin speed sensor, it might still work.
I have various speed sensors, cadence sensors, and heart rate sensors from various manufacturers including Garmin. I noticed my Garmin speed sensor (not V2 model) stopped working so I installed a new battery. I am not sure how long it wasn't working because it is hard to tell especially when using GPS but when I was doing hill workouts, I noticed my speed was jumping around a little. I confirmed it wasn't working and after installing a new battery, it still didn't work.
I noticed the positive aluminum terminal that is seated to the bottom of the battery housing wasn't aligned to the short positive copper FIXED post. I removed the paper / cardboard battery holder that has the 3 aluminum pinch extenders on 1-side and the larger single extender on the other that is suppose to touch the fixed positive post. In my analysis, I noticed it would not touch as it should. So, I took the cardboard marked with the "+" out and reinstalled it so it would touch the fixed post during the locking of the battery, after-which the LED lit up showing the unit was alive and working.
It is my hypothesis that the either during riding (vibrations) or unlocking the batter compartment, this cardboard piece rotates just enough so that the positive lead from the battery and unit do not touch.