When moving house most people order their broadband prior to occupying the "new" property and it should make no difference which provider you are going for or whether the present occupier has broadband or not so I fail to see why BT say you can not order until they have left.
Because you have left it this late it may mean a wait for up to a couple of weeks but that is the normal amount of time that BT quote. It could be less. Obviously your start date can not be until the present occupier has vacated the property.
If the BT systems or by calling BT lets you order now then just do that if that is what you want. You will be asked for a start date at that point and you will be offered that date or something as close to it as possible.
As @licquorice has stated. You are best to call BT to place an order and they will give you the correct information regarding time scales.
EDIT: I see that you have called BT already. I would call them again to see if you are getting the same answer and if it is ask for an explanation why you can not order it now with a start date after the present occupier has moved.
