I just reinstalled OS2008 without restoring my backup and the keyboard now pairs (Im using it for this post). Seems that there may be problems when upgrading and restoring a backup.