I may seem unfair, but if you see it from the perspective of Canada and USA, they are two countries where you have porous borders if you have residency and/or citizenship. I have seen cases where a person tried to illegally cross the border, another one was found in violation of customs, a transit passenger assaulting the flight crew etc. In all these cases the people were not legally present in the US, or were not here for more than a day. But, if a FBI background search is done, it will reflect these prior issues. And I am sure Canada is interested in them, and so would be the US.
There have been cases where with minimum documents an applications sails through, and yet in others it takes forever and additional documents. It is case specific, but I do not see it unreasonable.