Post Brexit Referendum employment theory According to Chuka Umunna, Labour MP for Streatham and prominent pro-EU campaigner:


  People were told: "if immigration levels fall, it will be easier to
  get a job, and easier to get a job that's paid well." Since 2016, net
  immigration from the EU has fallen. Yet this indicator has gotten
  worse.


He did not cite which study the numbers came from, but let's just assume it's true. From a purely supply / demand perspective it does seem counter-intuitive, but it could be more nuanced and complicated than that. 

My personal best guess was: this result could be from a lagged effect of all the previous immigration up until then. With the red tape and time needed to immigrate, settle down, get a sponsored visa, find a job, it may take months or years for immigration levels to have a measurable influence on jobs. I first envisioned conducting a lag / lead regression analysis to test my hypothesis, but have since redirected my interest in theory.

Question: Is there anything in existing economic theory that could explain a fall in immigration correlating and/or causing higher difficulty in finding employment? (note I use and/or for causality) And related, what other empirical findings outside the UK support Umunna's claim?

Further Clarification:


"easier to get a job": I am not quite sure how to quantify this section of Umunna's claim, I'm guessing he meant: average number of months unemployed before finding a job, or perhaps he meant: average availability of jobs in said sector. In your answer, explain which interpretation you use.
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.