I had the exact same issue. Try remove your sms protection thingy and then add the authenticator again.

If that still doesn't work, you gotta call/email Blizzard support. And if you're calling them, be prepared to be in a very loooong queue call. I waited for 1 hour+, but the issue was solved fairly quickly. Now both my Authenticator and SMS protection are activated.

Erm..try logging in to Battlenet (SEA, not US), and enable the sms protection. It might work or might not.