OK, then we'll have to start all over again.
Connect an Ethernet cable from one of the LAN <--> ports on the new router (there are probably four of them....choose any one that you want) and connect the other end to the WAN "O" port on the Time Capsule.
Power up the Time Capsule if it is not already on and let it run a minute or two
Open AirPort Utility on your Mac (Finder > Applications > Utilities > AirPort Utility)
Click on the Other WiFi Devices button
Click on Time Capsule
That will start up the setup 'wizard". You have to use this template for now, then make changes later.
The screen will look like the example below except that you will see a Time Capsule pictured

Network Name......Enter any name that you want. The wireless will be turned off later.
Base Station Name.....Enter a device name for the Time Capsule
Password......Enter a password to be used for the network and the base station
Verify....Enter the same password again to confirm
Click Next
The "wizard" will set thing up for you automatically. When you see the message of Setup Complete, click Done.
Now click on the picture of the Time Capsule in the AirPort Utility window
Click Edit in the smaller window
Enter the password if asked
Click on the Wireless tab at the top of the window
Change the Network Mode from Create a network to Off
Click Update at the lower right of the window and wait a minute for the Time Capsule to restart
Make sure that you are logged onto the wireless from the new router
Try to run a backup
What happens?