What version of Magento and have you applied the July 28 patches so Magento now recognizes Priority Mail Express as having replaced Express Mail?
There are two listed for each version except 1.7.x and they have to be applied in the proper order. The first one upgrades the Shipping Methods subsystem and the second one enables the USPS API & Service Name change.