This is the error I am getting at the moment when I try to log into iMessage. The same error occured when using FaceTime. I can use my appleID for the Appstore. Do you know what I can do about this?
This is a commmon problem with Hackintosh'ed computers. Is the computer you are using with OSX genuine?
Wether it is a real Mac device or not, the steps to fix this should be very similar. Here is a very long thread describing each step to fix this in great detail.
To start off, I would make sure that your Apple ID is verified. You can check the 'Verified' status of your AppleID by logging into AppleID's online management.