When your computer attempts to contact another PC, it will send an ARP Request out. The PC with that IP will reply with its MAC address. If there is no PC with that IP address, your PC will not get a reply, and (in Linux) your ARP table will show that IP as incomplete. So there is probably no problem on your end. Your ISP has probably not yet changed their router's IP address.
You can test your PC by running a sniffer. If you have a GUI, I recommend ethereal (easy and neat). If you do not have a GUI, I suggest using tcpdump. Run man tcpdump for help on using tcpdump. Once you run the sniffer, try pinging you gateway. You will notice that you send out at least 1 ARP Request. You will probably not see an ARP Reply though.
If you do not get an ARP reply, contact your ISP and tell them exactly what you did and that you did not get an ARP Reply. They will tell you what IP your gateway is using and when the switch will take effect.