northernpilot,
Well there is good news and bad news. You seem to be aware of the bad news; that you are not admissible until min of 5yrs from completion of probation. The good news is that once this is behind you I think you should have no problems getting hired seeing the way you worded your post concerning the DUI. You clearly see the mistake and take responsibility for it.
I was in your shoes and it's a tough to have to deal with this canadian waiver. The process is a pain. My eligibility date in canada was June of 2006. 6 1/2 yrs from making my mistakes.
Some suggestions:
-As others said, look for jobs that don't require flight into canada. Part 135 Charter/Cargo may be a good option after getting the 135 mins satisfied. Ameriflight supposedly hires some into the California system who are short on the mins for VFR work. I don't think Colgan flies into Canada so their route map may be worth looking at too.
-Look into expungement for your DUI. The state you offense occurred in either will or won't allow it. Find out and if it is allowed consider the expense of a good lawyer to get it erased.
-Another option for Canadian entry is to get a CANPASS. In a nutshell it's prescreened customs clearance and is valid for 12yrs. If your DUI is expunge-able then this would be the quickest option as a CANPASS takes less than 2 months to process vs. the 6+ mo for the entrance waiver and they accomplish the same thing.
I had a discussion with a Chief Pilot at my airline about these waivers on a recent flight and for what it's worth the common feeling is that the Canadian Government has gone overboard on this issue. I don't get the idea the airlines are worried about your mistake in this case so long as it's understandable. They are worried about you getting stuck in Canada while part of a crew and the delays/issues that would cause. So they are being very careful regarding these waivers, but I know SKW has hired folks who can't go into Canada (although very rare) due to the ability to have them on the EMB120's that don't go the Canada. So once you get your 1000hrs SKW may be a viable option for you as they are gong to be operating the EMB120's for a while longer. And finally Mesa, as you probably know seems to be desparate for pilots and this may work to your advantage.
Good luck!