Sorry this is all 2nd-hand info.
But there is a guided Trans-Africa tour currently underway, a group of 8 Finns on bikes. The group leader is a friend of mine.
They crossed from Sudan to Ethiopia about a week ago, and had spent over a day at the border, having difficulties to get into Ethiopia at all. Having been stamped out of Sudan, with no valid visas they had basically no way to turn back, either. They have carnets (also went through Egypt).
It appears they were helped out by our embassy in Addis Ababa, who sent some faxes to the border, where the embassy takes responsibility, that these bikes will 100% sure leave the country (or something like that - sounds weird, I know!) But then they were, finally, allowed to enter the country.
They also reported seeing other travellers stuck there in a similar way. And that the authorities at the border claimed these "new rules" (if there really are such things, and they werent just trying to extract money from these guys, for example!!) had just been put to effect only a couple of days prior to their arrival.