This is a result of an internationalization extension in X11R4 and the fact that HP is now using this extension. Emacs assumes that XLookupString returns the same result regardless of the Meta key state which is no longer necessarily true. Until Emacs is fixed, the temporary kludge is to run this command after each time the X server is started but preferably before any xterm clients are:
xmodmap -e 'remove mod1 = Mode_switch'
NOTE: This will disable the use of the extra keysyms systemwide, which may be undesirable if you actually intend to use them.