I had a similar problem but it was with an Arduino clone. Some how the uart was not recognized in the 1.0 IDE, but the skripts could be downloaded using an earlier rev or the chips interchnged with one that had a downloaded sketch with no problem.
If you have two authentic Duemillanove purchased at the same time, this sounds unlikely, but It might be worth a try loading a pre-1.0 rev and trying it.