error registering new chef-client

Getting this error on a new chef client:

/usr/lib/ruby/1.8/net/http.rb:2101:in `error!’: 404 “Not Found” (Net::HTTPServerException)

is actually caused by having an old chef-client. Took me a while to realize, and google was not that helpful.