It should only take two weeks to process. If there is an issue with your sample, it could take four weeks. After the four week point, it usually means your sample was not sufficient enough (for whatever reason) and you'll have to resubmit. How ODD that it took them almost five weeks to receive the test!
My husband's Y-DNA test was 'in the mail' for almost a month, too. And it's taken nearly three weeks now to process.
I am waiting for them to receive my THIRD ancestryDNA/autosomal test. Third time processing. They SAID they mailed it on the 7th of March, but it took over TEN days to get here.