I'm also a little puzzled why he isn't a U.S. citizen already.
My Mom's been living in the USA for ~60 years, nearly her entire life, yet is still a Canadian citizen (having moved to the USA with her family when she was a few months old). It isn't so much having a strong connection to Canada as it is apathy. She just never cared about politics enough to bother jumping through the hoops of getting citizenship.
But I'd think that if one had a spouse who's a US Senator, one might have some incentive to go through with citizenship, so as to vote for him/her. Good thing Gillibrand's seat is safe. Imagine if she was in a close race, and ended up losing by one vote!