It was filmed in Tunisia during Episode II, but reshot on a green screen set during production of Episode III. The reasons for the reshoot aren't clear.
Photos here:
http://www.starwarz.com/tbone/index.php?categoryid=14&p2_articleid=324
The on location version should have been on the Blu Ray extras. Darn it!
I've been puzzling over a photo of Lucas and Jango Fett that looks like Tunisia too.
