For the sake of anyone having a similar problem and finding a fix for it, I thought I'd make a little more noise. I'm about 200+ Pokemon into the game. All badges, beat Red. So, restarting doesn't sound too kosher for me. If anyone would like to load my game save and see the issue themselves, I'd be more than happy to upload it, I'm out of answers. I just know I'm not too happy with a Pokemon game with the inability to trade. :l