Then I strongly suspect that this is a hosting issue.
The fact that your host didn’t recognize the gettext function already tells me that they aren’t very familiar with WordPress, because that’s just a standard WP tool, so I’d suggest moving to a managed WP host.
@karyn, so you’ve already tried these: make sure the user is logged in, that his account has the access required for the protected page, and you also tried deactivating other plugins and themes, and turned caching off for the page. Correct?
I’d try a couple more things: in a separate directory, try creating a new, clean installation of WP, protect a page the way you did for the one you’re having trouble, a user with the same access, and test there if you can reproduce the problem. Next thing I’d try to rule out the server as the cause, I’d try that same thing in a different web host, could even be a local server you install in your computer.
I know it seems tedious, but you’re having a very unusual problem, and it’s important to find where the issue is coming from. You seem to have ruled out plugins, themes, caching, and I think you could rule out a possible issue with your WP installation, and then the server environment. Once you figure out where it’s coming from, it becomes easier to place where the problem is.
I hope that helps!