Public bodies have 20 days to provide a response. If they decide that there is a case for refusal, they can respond saying they are doing a public interest test and thus have another 20 days before they have to provide the next response, thus in reality they have 40 working days for complicated FOI requests.
They can legitimately go past that 40 day deadline if there are good reasons, for example having to consult with a foreign government or a company before releasing a document. They need to try to avoid having to do this though and at all times they should be telling the FOI requestor what is going on.
An open and transparent government is great until you realise that you actually need to pay for it! Cutting the staff means people actually doing the work have to stop and deal with the FOIs. Morally fine from a transparancy point of view, but in reality FOI is much abused by journos and other interest groups who are trying to get civil servants to do the bulk of the work for their benefit. The whole process is bureacratic as hell. Having said all that, the Home Office is notoriously incompetent and no doubt deserves the kicking it is getting from the ICO.