There should have been an option to "Change card" that you could have used instead of removing the card. Removing the first card might have automatically canceled your subscription to the game.
To put a new card on file, you'd have to go into your game account and re-subscribe with the new card. If it shows you still have an active subscription, you'll have to un-subscribe, then re-subscribe with the new card information.
It's really weird. There's no "add a card" or "add a new card" option. Instead, in the column on the right, click on the icon & name of your CoH game account to pull up the Game Account Details page.
In the section titled Actions, click on either Subscribe to Game or Purchase Additional Time. They're the same link, so it doesn't matter which you click.
When you add more time, it will put your new CC on file. Note that it won't charge the CC until your current billing cycle is up. That's a good thing, in that it keeps your card from being charged if you don't currently have the funds, but it's also a bad thing, if you have the funds for, say 2 months, because you have to wait a month before you can add another one. 
[ ProTip: The banner is a link to art refs!! | The Khellection | The HBAS Repository | Brute Guides (4/16/10) | How To Post An Image - A Quick Guide ]
Biggest Troll on the forums? I'll give you a hint:
On plaync.com I removed my credit card so that I could add a new one.
I was able to remove the one on file with no problems...but now there is no option to add another card.
What do I do to add another card?