I think the problem is that unibyte characters in an unknown encoding — which is what non-ASCII characters are in a binary file — are represented internally with character values #x3fff80–#x3fffff.
Arguably, not taking this into account is a bug in nhexl-mode, or at least an incompatibility with MULE and Emacs ≥23.
A possible fix is to switch the buffer to unibyte mode. The code below does this automatically on entry to nhexl-mode. Note that it doesn't restore multibyte mode if you switch nhexl-mode off.
(defun my-nhexl-mode-hook ()
;; Turn off multibyte, otherwise nhexl 0.1 displays non-ASCII characters
;; in hexa as values in the range 3fff80-3fffff instead of 80-ff.
(if (and (fboundp 'toggle-enable-multibyte-characters)
(add-hook 'nhexl-mode-hook 'my-nhexl-mode-hook)
This feels more like a partial workaround though. It would be nice to be able to display multibyte characters in the text display and individual bytes in the hexadecimal display.