I think ron_s is getting at this... the gist of it is, you can't with core alone. This is an unfortunate side effect of the roles module being developed 6 months before the recurring module was actually put in core. So what we have are two systems that should work together but don't. I'll respond more to ron_s's posts directly here in a bit, but basically what you can do is either accommodate this in a custom recurring fee handler or work through an existing one. For example, I integrated Auth.Net's ARB service in the core Auth.Net module. I invoke a hook whenever an ARB payment is received, so a custom module could implement that hook and update a user's roles accordingly.

However, as is apparent in this thread, core really really needs to have a way to associate a role promotion with a recurring fee. It also needs to better understand what to do when a payment fails... when do you decide a payment is late and should reactivate a previous role w/ an extension or a payment should be considered as repurchasing an expired role? Perhaps ron_s's idea of creating a new order when a recurring payment comes in could solve this.

@ron_s - regarding your bug from uc_roles_order(), I fixed a similar bug in the files module but didn't think to check this module (they were written by the same developer). I'm going to go do that right now and will come back to this thread. I'm running behind on a project and need to devote a few hours to it atm.

fwiw, associating roles to recurring fees is something that is on my radar and will be possible in the 2.0 release.