The answer is that nokogiri is currently broken somehow (there are few vaguely related open tickets on github, but nothing specifically relating to this).
Anyhow, you have to use hpricot (despite it being EOL) for this to work.
Be aware that hpricot won't install on OSX cleanly, and currently requires:
sudo ARCHFLAGS=-Wno-error=unused-command-line-argument-hard-error-in-future gem install hpricot --no-rdoc --no-ri
All in all; messy and bad.
Simple solution: don't use premailer.