iPhone 4S to new iPad - iMessage does not work
Try turning off iMessage in Settings, reboot the device, and turn on and log into iMessage again.  This should re-register your device with Apple's iMessage servers, and may resolve your problem.

This has fixed a similar issue for my iPhone in the past.