[everfrustrated]

If you've previously been denied a visa you're no longer able to use the visa on arrival system. Hence you need to apply for a visa before you travel.

[mjevans]

I think the question is: why were they even let in at the border crossing if it wasn't a valid entry? Shouldn't they have been turned back there?

[deskamess]

Very likely, that as a Canadian, you can enter the US without a visa as long as you do not work. You need a TN visa+status to work. So probably entered US on passport (no visa status) and then applied for TN... during which things went poorly.