Upgrade from rpm-3.x is a tad bit hard, when the rpm-4.x RPM file is in v4 format -- which you need rpm version 4.x to install. Doh!
Use RPM 3.0.5 which understands RPM 4 format.
ftp://ftp.rpm.org/puvb/rpm/dist/4.0 has rpm-4.0 in v3 packaging.