I believe I've figured it out. I must have an old version of 'htmlize' installed somewhere, I 'edebug' traced through the code and fell through to this part:
(when lang
(if (featurep 'xemacs)
(require 'htmlize)
(require 'htmlize nil t))
(when (not (fboundp 'htmlize-region-for-paste))
;; we do not have htmlize.el, or an old version of it
(setq lang nil)
(message
"htmlize.el 1.34 or later is needed for source code formatting")))
I couldn't manage to set up my load-path to load htmlize 'properly' (is htmlize not able to be loaded via 'load-path' and 'require'?), but after downloading htmlize 1.43 and adding the following to my .emacs, I seem to be in business again:
(load-file "~/share/emacs/site-lisp/htmlize/htmlize.el")
Thanks everyone.