There is already a second Mario & Sonic Olympic Games set to take place at the Vancouver 2010 games, which I personally find neat since I'm Canadian. I might just have to buy it because it's the one and only time Mario will make it to Canada I imagine!
At any rate, I heard the original game didn't fare too well in the ratings, so even though it's got local kitch factor, a sequel might not be that great. I've never played the first one though, I'm only basing this on the ratings it recieved.
I think Sonic would fit well in the Mario Kart universe, but I don't care too much for a lot of his supporting cast. Sonic, Tails and the bad guy (I always though he was Robotnik from the cartoon, evidently he goes by the lamer name Eggman?) are good candidates, but I don't need the whole hedgehog gang jointing Kart. Just like Sonic's appearance in Brawl, it would be a good cameo.
Other than the above, I don't think the characters mesh well enough to have a story-driven title. It might seem a bit forced. An RPG would probably be the best idea over a platformer, but I personally don't want their relationship to continue beyond the casual sports titles.