Not there yet, but close.
Colors are a bit dull. Is there a reason you left S in SKY out when you put a tag line below. Briefly, needs formatting. Zoom on and check your alignments. The (R) mark is way too close. Give it some room. The logo says SKY and you use spacious fonts but not spacious enough to convey the openness of the sky and the broad search capabilities. OK, ho do I put it... Change the fonts. Right now it looks awfully close to SKYY brand (
http://www.skyy.com/)
The logo (arrows/box) looks OK but has a feel of a sketch. Work on it more, add some meat to it and give some style.
Overall the three elements image+name+tag line need better integration.
I'll check your site next time I'm going to Europe.