Okay. Something you said sparked a memory in me. The last website I put Hikashop on had the same problem. It ended up being in the workflow. The log in screen, shipping methods, payment methods and cart all came up on the same page. Since I hadn't logged in/registered yet the UPS plugin didn't have the information it needed to bring back a rate. So I changed the workflow to have log in/registration page on step one, then shipping method, payment method and cart on step two.
I thought this would take care of the problem but nope...