Got the same problem here.
-Drupal 5.7
-Ubercart 1.0 RC2

It doesn't seem to be a "uc_coupon" bug to me.

There is a test option in "free_order" called "add discount", when I use it to bring the total below zero I always get "We cannot process your order without payment." (same thing with uc_coupon 1.5 zmove version)

I did a bit of debug, "order_total" seems to be updated but too late, or something like that.
As its stay over Zero, "free_order" deny the checkout.

I tried a couple of fixes without luck...
Hope someone can find a proper fix!
Thanks.

PS: Also tried with today bazaar code with no luck.