Tony,
First port of call is the manual for your mobo, to check for specific procedures about replacing your CMOS battery - e.g. any jumpers or DIP switches that need to be reset.
If it's a standard Li-ion coin cell battery you shouldn't have any problems - be careful with any delicate clips and ESD, of course. Best to use a plastic object to prise it out - and avoid magnetised objects for the task!
Replacement batteries are easy to source online (less easy to find in your local Boots or hardware store, though you might be lucky). All coin cells have the type engraved on them which makes it easy to get the right replacement.
If you haven't already lost all the BIOS settings, note them down before removing the battery (although it sounds like you have, with your PCI Express problem) - otherwise the system will revert to defaults.
I'd be a bit concerned about the need to poke the battery, though - that sounds like a poor connection rather than flat battery.
SD