If that's their REAL concern, it's easy to just add one sentence on the offer letter, such as offer contingency on the approval H1B application,.. and on that you can start on Oct 1, 2006,...
But again, if that is the real reason they don't want to give you the offer because that usually is just an easy excuse.