cordelli, you are a godsend. Although the problem wasn't exactly in connection sharing for the base station, your last comment gave me some ideas and I started mucking around with the Airport Express configuration. I remember reading something about setting the TCP/IP configuration on both the Network System Preferences and the Airport Express itself. It turns out that the TCP/IP setting on the Airport Express itself was previously set to "Configure Manually" and not "Using DHCP" which is what it should be. So all I did was to change that last bit of setting and everything's cool. Thanks for leading me in the right path.

The real mystery now is how the AE worked at all in those other hotels. I'll get to test that when I return to the hotels that I previously stayed at.