Dumb question but your iPad is wifi+cellular data?
Yes it is.
Hmm, pm me and I'll give u access to a old account see if it lets u do it if so then you know it's something to do with your Apple ID, have you updated the terms and conditions? I don't use my Apple ID for iMessage sorry..
This is a good idea. I logged in with my other Apple ID, the one I use for iTunes purchases, and it worked right away. I did update the T&C for my other one, it let me download apps after doing it.