When you removed the CMOS battery, you also made sure that the main battery and the AC adapter were unplugged, right?
Leave the battery out overnight, with absolutely nothing connected to it. If it still doesn't work, that link on how to reset CMOS password is your best bet.