If you are currently working in H-1B status, you may begin working for the new H-1B employer upon receiving the RECEIPT from the H-1B filing (normally around one week). You do not need to wait for the actual approval notice.
If you do file via premium processing (an additional $1000 fee to the government), then you will receive a response (approval, denial, or request for additional evidence) within 15 days.
