If he's swimming around, acting normally, not breathing heavily, then he'll eat when he's good and hungry. I got a Majestic from my LFS two weeks ago. They gave him to me because he wasn't eating. I put him in my tank and he never hid for a minute, he started swimming around, normal breathing, but he didn't even pick at the rock, he showed no interest in eating. As long as he acted normally I knew it was just a matter of time, and sure enough, he started picking at the live rock. He didn't eat the brine/mysis that I give everybody else so I threw in an Angel formula cube and he went to town on it, and slowly he's starting to eat what I give the rest of the fish.
Like I said, if he's otherwise normal in all other respects, give him time.