Hi Paul
You can do this on a linux box with a pretty much basic kernel.
I currently have a similar setup at home with a DSL and a cable line (from different providers).
Here's the script I'm actually using: http://ocaholic.ch/download/multinat.txt
Some packets are tagged with iptables (SSH as an example) because I want it to prefer the DSL connection. You can do pretty interesting things with it, even per-packet round-robin distribution … which is a Bad Idea™ though.
If you want it to fail-over automatically you need to patch the kernel etc. You'll find all information on http://lartc.org/ (especially on http://lartc.org/howto/lartc.rpdb.multiple-links.html) and here: http://www.ssi.bg/~ja/#routes
This setup is running for about a year now and it does this quite well.
Regards