The Leonardo might work for me if it has 2 serial ports as you say...
And it might not as the Leonardo can bring its own limitations to the table, and I understand the software serial library Lefty mentions is written with exactly this in mind, for the Uno you already have, and it is free.
What limitations?