Evidently, part of the upgrade to Ubuntu 15.04 involves an upgrade to gnome-terminal that removes the old feature that allows new terminal windows to be opened as a tab, instead of a new window.
If I had known this before the upgrade, I literally wouldn't have upgraded. Full stop. I manage many servers, and having an SSH client that allows new sessions in a tab is essential. Opening new windows for 15 servers is completely unmanageable.
In this screenshot, you can see the "open sessions" menu option. There used to also be an "open tab" menu option, with the complete list of sessions I have saved. It's gone now.
Best Answer
Just downgrade to good old 3.6.2 like me did.
If you have a 64-bit install:
For 32-bit: