I reported the problem on itunes as scubidoobie suggested. The reply I received was not helpful at all. They recommeded consulting the Apple support page for keynote remote, which is where I started in the first place. I agree that we should all bombard Apple via itunes about this problem (see scubidoobie's reply) and get them to fix it.
I found a workaround on another posting, which is clumsy but worked for me. It may be a solution until Apple updates the remote. The idea is to use another app that can link the 2 devices by bluetooth.
1. Get Pic transfer lite (free app) and install on both ipad and iphone (or ipod touch).
2. Activate bluetooth on both devices.
3. Launch keynote on one device and the remote on the other device.
4. Launch pic transfer on both devices and follow the prompts to sync bluetooth
5. Now double push the home button on both devices to pull up the multi-tasking bar
6. Open keynote and keynote remote on the relevant devices.
5. In keynote, go to settings, advanced, remote. You should now be able to link the remote - on the device running the remote, you may need to hit settings and then 'new keynote link'.