I've spoken with a lot of people about Randy Couture in the last day. Things are definitely happening.
First, I can say with 100% certainty that there are current negotiations for Randy Couture to return in November to main event, and that the current proposed opponent is Brock Lesnar. They can't get Fedor, too many issues to work out on short notice, and he has a US-only non compete with Affliction.
This will be a new contract, not a return to the old one. It will likely pay him more and give him more benefits, but it will lock him into the UFC for the long term. In exchange for signing it Zuffa would drop all breach of contract charges.
From there, things get hazy. Randy is now training full time as if he is expecting a fight soon, but he still hasn't signed anything as far as I know. As far as the details of the Lesnar fight, I don't know if it's title or non title.
Update: Dave Meltzer is now confirming the story:
A source close to Randy Couture has confirmed today that Couture is in negotiations with UFC for a new three-fight deal which would end the nearly nine month legal battle between the two sides.
If the deal is closed, and the source said they are hoping to conclude negotiations and announce the match sometime within the next week, Couture would face Brock Lesnar on 11/15, most likely in Portland, Oregon.
Couture was said to be hoping that if everything went well, the next two fights could involve Fedor, Nogueira, and/or Chuck Liddell. However, all previous hangups involving Emelianenko and UFC remain.
According to Ariel Helwani at MMA Rated, the UFC is planning to announce this deal on Tuesday if all goes well. He also says the UFC is considering an M-1 proposal to have Randy fight Fedor in his second fight:
Believe it or not, the UFC is also considering a proposal from M-1 Global to co-promote a Randy Couture vs. Fedor Emelianenko bout following the Lesnar fight in November. The third proposed fight would be a bout against either current interim heavyweight champion Antonio Rodrigo Nogueira or Chuck Liddell - depending on where both fighters are in their respective careers. However, given the nature of the fight game and the fighters involved, it's hard to predict what will happen that far in advance.
Things are getting very exciting very fast.
Update: Some possible cold water from Dave Meltzer:
Dana White is adamant that nothing is happening right now regarding Randy Couture and UFC, and nothing has been talked about since Tuesday.
I have reason to think he is not being entirely truthful, but who knows. There's a reason every website is hearing this now, and a reason Randy is training full time again. I believe this is an effort to keep the focus on Rashad Evans vs. Chuck Liddell a week from today.