I found the problem but still not sure why it doesn't work!

I used the USER_NAME() and SUSER_NAME() functions to check the before and after and found that SUSERNAME() returned dbo before the switch (EXECUTE AS) but returned Domain\UserA after the switch.

I moved the WITH EXECUTE AS into the procedure itself and changed it to EXECUTE AS USER 'Domain\UserA' but this still failed, however changing it to EXECUTE AS LOGIN 'Domain\UserA' worked.