The subnet of IPs the datacentre gave us was apparently on loan, so they assigned us a new block and gave us two weeks to swap them over, during which both will be active. They're on totally different networks and subsequently have different gateways. The machines are a mixture of Debian, Ubuntu, Windows 2003, Windows 2008 R2.
Is it best just to add the second gateway with a higher metric (numerically speaking)? Most of the documentation I've found for running multiple gateways has been under the assumption that both will be active indefinitely. Whereas I'm after more of a failover model.
Adding a second IP address and another gateway might be a problem indeed. Dead gateway detection mechanisms are not very sophisticated and far from perfect. Also, your ISP might be doing Reverse Path Filtering and thus preventing any kind of asymmetric routing.
What I would do is making sure your new gateway would route your old subnet's traffic out (chances are that it is the same router interface simply with another IP address added to it) and simply exchange the old default route for the new one after setting up the IP interface aliases with the new addresses instead of adding a new default route.