AngelaL,
I am in a similar situation as you are now. With the exception that my work permit paperwork started 7 weeks ago. I was told it shouldn't take more than three weeks, but five weeks after I sent the paperwork to my employeer I got an email asking for yet more paperwork. Then, a week after sending the extra paperwork and inquiring about the status of my workpermit I got an email from my employeer...the lady in charge of my case have been out from the office and she was just then going to give my paperwork to the work permit consultants and ask if that was what they needed for the work permit. Last I knew I had a June 5th start date, but with no work permit after seven weeks I am not sure I will make it!
I will highly recommend that you keep close contact with your employer. I am sure they would push back the start date if needed. They really cannot control the WP process, but I am sure they can accomodate you.
good luck!