I'd also agree with the Duemilanove board. If you really get skint for output pins you can consider multiplexing.
Chances are, once you get to the level where you need more pins you'll find uses for your 'old board'
In the UK at least, the Arduino boards still gain a very high second hand value price - worth noting.
As the other guys have mentioned, Duemilanove has so many shields which are compatible jumping across to the Mega1280 may end up costing you more. I'd wait till it's a ltitle more accepted.
If money isn't an object, consider picking up both...