Hi Joe,
I can't tell you about Tunisia and Libya, but we were in Sudan in January and found it pretty easy as long as you are patient and follow their rules.
The bureaucracy is a bit overboard, but it appeared to us that it also depends on where you enter. We had a lot more checkpoints etc. where they wanted to go through all our papers coming from the west, than a friend of ours who came up from the south.
It took quite a few hours to go through all the differant border officials (customs, police, intelligence, medical officer, and a couple of others that I don't know what were!) and fill out all the forms. But all in all I don't feel it was too bad. Maybe we were used to african bureaucratics by the time we got to Sudan.
The most important thing when entering Sudan is to list every possible place you might want to visit. This is written down and isn't easily changed, although you can with a lot of hassel, and it isn't for free...
How (where) are you planning on entering Sudan? As far as I've understood, it isn't legal for forigners to cross from Libyas south eastern corner into Sudan. Are you driving via Egypt? Or flying over?
Since you won't be coming via the Darfur area where we entered, you probably won't have any security problems.
Visiting the pyramids etc. is a must and when you arrive in Khartoum, there are some nice museums that are worth visiting to see some local history.
One place to stay away from in Khartoum is the Blue Nile Yachtclub. There was litteally $hit everywhere in the showers, etc. when we were there. We ended up staying at the Youth Hostel. It was a little better and more central.
All in all, we stayed in Sudan about a month and generally enjoyed it. The main downside is the attitude towards blond women. My wife got hassled a lot, even though she used long dresses, long sleaved shirts and usually a bandana or something over her hair. This also happened with other light haired women we met along the way. She never walked around alone, and we would get constantly asked if she was my sister, and if they could go on a date with her!!! I don't think it would be a safe idea to try it the other way around and ask that of their wives! Of course, if you visit an internet café in north africa, and have a look at what the majority of surfers are veiwing, you'll see that it's porn with blond bimbos... So in their minds, all blond western girls must be easy... They seemed pretty sexually frustrated there, and in the other islamic counrtys we were in. Next time she'll dye her hair dark so she won't stick out so much, just to make things easier for herself!
Have a look at our website under - Sudan. There might be some more stuff if interest for you.
Good Luck!
Erik D.
www.dunia.no
------------------