If a UN force enters the country with Sudanese consent, it will be a UN force too ineffectual to accomplish anything, just like the AU force.  It may even end up fighting the rebels instead.

We need a large, heavily-armed NATO-led force of 50,000 troops or more that is prepared to go to war with the Sudanese government.  The troops could come from countries as outlined below.

15,000 Africa
10,000 Asia, Latin America
 1,000 Canada
 4,000 Japan
15,000 EU
 5,000 Russia and Eastern Europe

These are admittedly not much more than wild guesses, but I think achievable with enough political will.

The US won't be able to send ground troops after the Iraq debacle, but might be able to help with logistical and air support.  The UK will have to withdraw from Iraq in order to do this, and Canada would need to pull out of Afghanistan.

China is the main buyer of Sudanese oil, but I think they'd back down if the rest of the world was really serious about intervening.

Darfur was an independent state in precolonial times and there is no reason for it not to be again.  After it is liberated, expect about 20,000 troops to remain for at least 10 years.

It was done in Bosnia.  It was done in Kosovo.  If it could work for white people, it can work for blacks.