My former employer - Efficient Frontier - put out a study yesterday comparing Q4 '07 to Q4 '06 across the 3 major SE's and looked at both spend growth (29% Y/Y) and ROI growth (13% Y/Y). That's across ~$500M in annual spend and I take it to mean that spend is growing far, far faster than ROI at this point.
Its a trend in every niche, not just travel. As more and more advertisers sign up, which is happening in droves, there are more people bidding and bids are driven up. Also it would have always have been slower in January as most people have spent a lot during christmas and the new year and are generally rebuilding their bank rolls at this time of year.
Only advice I can give: Increasing your CTR on Adwords will decrease your CPC and should help out with ROI as a result.
Untill then, good luck and if you do retry towards the start of March, please keep us updated.