The reason for this can be a lingering old version of package.el
in your load path. package.el
was officially included in GNU Emacs 24, and the downloadable file for earlier Emacs versions doesn't support dependencies on built-in packages (emacs-24.1
is considered a built-in package here).
Type M-x locate-library RET package
to find where Emacs is getting its package.el
from. The path it shows should end with lisp/emacs-lisp/package.elc
. If it doesn't, try getting rid of the indicated file (or changing the load path so Emacs doesn't find it).