Most companys pay between 1 -2 weeks behind depending on the pay cycle. This is normal, not just because you are new and need to be inprocessed. Most HR/Payroll departments can turn the papers aound within 2 days after you provide the information that they require.
If you get desperate, ask for an advance.