Upgrading from Sat 5.1.1 to 5.3 on RHEL4 is not possible: After several attempts at this it seems that it is not possible to upgrade to 5.3 on RHEL 4. The primary issue is dependencies and order of steps to perform upgrade. First, the updating of the certificate comes later in the upgrade steps; however, many dependencies are not available until you are subscribed to the Satellite 5.3 channel. Second, several dependencies can only be satisfied when subscribed to RHEL 4 development channels. Finally, elfutils-libs appears to be a dependency; however, it is only available in the RHEL 5 channels.
What's the name of the 5.3.0 ISO file you used? Are you absolutely sure you did not use the RHEL-5 version? For RHEL-4, x86_64 the iso you are looking for is: redhat-rhn-satellite-5.3-as-x86_64-4-embedded-oracle.iso or in case you use external database: redhat-rhn-satellite-5.3-as-x86_64-4.iso
Private comments indicate resolved through Support. Closing bug out.