I recall having this exact same thing happen. I know you say you changed the batteries. Make sure the new pair is new and fully charged. Use a battery meter / test gauge and make sure they register as "good". The red light coming on only indicates the flash powered up and it will, even on weak batteries. If it doesn't have enough full power it won't fire. You can also try using manual mode and make the setting as minimal as possible which should require less power..see if that works. Also, be sure there's nothing in front of the sensor (any particles) . There may also be additional tips in the manual or you can also call Canon at 866-261-9362..support is rather helpful.
