Post Brexit Referendum employment theory
Is there anything in existing economic theory that could explain a
  fall in immigration correlating and/or causing higher difficulty in
  finding employment?


In addition to the lagged effect you outline, there are at least two possible causes for the paradox you describe. These theoretical possibilities are independent of which interpretation of unemployment is adopted. I'm unaware of (and not even searching for) statistical evidence of whether this actually occurs. 


A reduction of immigration could also entail a reduction of demand of goods and services. If there's no demand, some businesses are likely to reduce their staff, leading to an oversupply of labor (i.e., unemployment).
High-skilled immigrants might boost the industry in a different country to an extent that renders that foreign economy more competitive than the domestic economy. A significant trend in that direction could prompt domestic companies to slash jobs or even to relocate to one such country where supply of high-skilled labor is stronger. That would lead to the unemployment of low-skilled workers in the domestic labor market.


As for 2., it is reasonable to say that --almost by definition-- the low-skilled workers outnumber high-skilled ones.