How to programmatically create a node when a payment is successful
Looks like hook_uc_checkout_complete() is called while the order is still in "in_checkout."

You might want to consider using Ubercart's Conditional actions module and add an action for "Trigger: Customer completes checkout"; it allows you to execute actions based on a range of conditions. You can then either execute custom PHP code to create the node, or implement the hook_ca_action() (see "ubercart/ca/ca.ca.inc" for reference).

As to how to programmatically create a node, you can either use node_save() or drupal_execute(). There's quite a few tutorials around that you can use as guidance.