Hello,
does the UPS start to work when you switch SEO off?
I tried to test it with VirtueMart 1.1.4, but there is some bug in the UPS module. I just got
Fatal error: Call to a member function getText() on a non-object in .../administrator/components/com_virtuemart/classes/shipping/ups.php on line 172
So I guess the UPS code is a bit weird.
Unfortunatelly, I cannot see a direct relations between it and JoomSEF. Also, as you have been asking about the URL in checkout not being SEF, the reason is that having checkout URLs in SEF format has no affect on your site SEO ranking and would be making things just ore problematic. That is another reason why I think there is not a direct relation.
Anyway, testing the behaviour with SEO off might help.