Are you trying to link with a Mac using Keynote remote on your iPad, or are you trying to link to your iPad Keynote app using an iPhone/iPod Touch with Keynote remote app? You don't say.
If the first case:
1. Open the Keynote Preferences on your Mac and click on the Remote tab - ensure that "Enable iPhone and iPod Touch Remotes" is checked. If it is, sometimes it is best to reset the link - in the Remote Preferences, click the "unlink" button to break the old link, then uncheck the "Enable..." check box and then re-check the "Enable..." checkbox.
2. On your iPad Keynote Remote App you should now see "authentication failed" and instructions to delete the link and try again. Tap "Link to Keynote" and on the next page, Tap "New Keynote Link..." to reveal a set of numbers.
3. At this point you should see on your Mac that your iPad is now in the list of devices in the Keynote > Remote Preferences. Click on "Link" and type in the numbers from your iPad. This should re-establish your link.
See if that works.
Thanks for the pointers. I am using an iPad2 and an iPhone 4s. I have successfully connected using Wi-Fi now. Apparently there was an issue with the network firewall. After trying another network, I was able to connect. However, I am still incapable of connecting using Bluetooth. What might I do to troubleshoot Bluetooth connection failures?