This comes from a time where SEGA was no longer in the console manufacturing business, during the GameCube, XBox, and PS2 era. From Yuji Naka:
“So yes it is true. Back in the day I did go to Kyoto to visit Nintendo and wanted to have a meeting with Mr. Miyamoto and figure out could we make a game maybe with Mario and Sonic together. Although those original conversations happened about three years before the Olympics game came out, we weren’t able to really make a game that featured Sonic and Mario back from that original conversation, but because we had those conversations, it kind of kicked off future conversations with Nintendo which afterwards led to the Olympic game coming out.
The original Sonic becoming a part of the Smash Bros. game was also part of that conversation. During the GameCube development for Smash Bros., he really wanted to get Sonic into that game, but it was just too late in the development process and couldn’t get it in for GameCube, but they did move forward and put Sonic in for the Wii version.”