Write to UPS, tell them that said package was NEVER received.

Once they they dig up paperwork to the contrary, it should also show that you collected the package and therefore paid for it up front..

-ml