I have just travelled through Tunisia for almost 50 days, and I'm now in Cairo.
I blitzed through the PDQ course mentioned above before I left the UK, and I also had some lessons through my Uni (UCL in London - the lessons are available to non-students, office is at the top of Gower Street). The PDQ course is OK, but not fantastic. I bought it becauise I have had good experience with Linguaphone, but you're probably better with the full course.
Aside from a few phrases and words, it has been mostly useless, for the same reasons as Geoff found. You're probably better off just learning a few phrases (water, name, greetings and salutations, "no arabi" etc etc)
For where you're going a good conversational French knowledge will be FAR more useful. Be warned that the others are right - Arabic is fiendishly difficult and variable: phrases from my Lebanese teacher were useless in Tunisia, and phrases from Tunisia sound like nonsense to Egyptians.
In some places in Libya, Italian and English will be OK.