I don't think HTML::Format exists anymore, and that's why you're getting these messages from CPAN.

Try:

 i /HTML-Format/
[download]

and

install SBURKE/HTML-Format-2.04.tar.gz
[download]

I guess the confusion is that there is no module named HTML::Format. The modules are named HTML::FormatX where X is PS, RTF, Text and ter.