Didn't write the error message down, of course. Something about MELPA looking for a package version from two months ago and deciding the package was "Not Found".
Eventually figured out I need to run package-refresh-contents, which grabs the latest package listings. Might be overkill to run that automatically in every Emacs session, so I won't add it to my .emacs.
I will add a comment though.
;; Package not installing? ;; Try 'M-x package-refresh-contents' (require 'package)
Hopefully I remember to read my own comments.
Or the documentation.