If I remeber correctly I went with these guys, from B'ham to Sharm:
http://www.ittio.co.uk/ITTIO/home.aspx
It cost me £180 , but I think you can get better deals if you book in advance.
It would be also very usefull if someone can arrange and send taxi for you from Dahab. That should cost you £15-£20. Airport taxi can charge you as twice as much (subject to your negotiating skills).
