the haven of peace and tranquility that is the Middle East? Even the remote resorts of Egypt have attracted the attention of bombers.Oman and Bahrain are working on making themselves beach resorts. And I went on a tour of Iran a few years ago; absolutely wonderful. Syria is fascinating too. But all these are places that Bush might decide to nuke at 45 minutes' notice.
Have you thought of resorts on Turkey's southern coast?
I second Iran - a fascinating place and the people are very hospitable. Costs are relatively low. The downside is the difficulty in getting a visa - the rules keep changing and the official line does not favour westerners. Having said that, the public attitude is quite different from that of the government. There are plenty of flights, October is a good time weather wise.
Turkey's out of the question as I can't go there because of my work. Sharm-El-Sheikh - Been there before and have to say it was a bit too touristy for me. And the scuba diving is much better from the Jordan side of the Red Sea IMHO.