There is an art, and a lot of guess work, into getting the ISP's modem and a router to synchronize.
First, some questions.
What do you mean "the service gave me a new IP address"?
What is the IP address on your computer? You can find this by opening a Command Prompt (Start>All Programs>Accessories>Command Prompt). You will get a black window with a blinking prompt; type: ipconfig /all and hit Enter.
It will give you a lot of info. What you are interested in most is the Description (which is the name of your network card) and the IP Address. Send me this info.
What kind of router is it (brand and model)?
How are you checking connection (wired or wireless)?
To get the modem and router to sync, turn both of them off or unplug the power for a few minutes. Plug the router in and wait a minute or so, then plug the router in.
The router gets the real IP from the ISP modem. The router gives your computer a local IP address from its pool (which usually starts at 192.0.0.0), not the same one from your ISP. The router passes data from computer to ISP, converting local IP to real IP as needed. The two must be in sync. Your computer should show an IP that is different from the one your ISP gives.
After doing this and you still can't use the router, go back to the Command Prompt. Type: ipconfig /renew and hit Enter. This will take a few seconds/minute. Lights on the modem and router should blink.
This commands the computer to renew it's IP address. If the router and modem are in sync, you should get a message with an IP like 192.0.0.X and be able to get online. If you are getting this address and still cannot get online, make certain the modem and router are connected properly. If you are checking online status through wireless, try it through a cable by plugging a network cable into computer and router.
Let me know if this helps and answers to my questions above.
Dewey