Technically our use of any of these trademarked and copyrighted images is never legal. Sega just doesn't do anything about it because they seem to like the publicity. Out of courtesy, you could just put "original game by" above the Sonic Team logo, so its not as though you're implying they worked with you on it.
Nintendo has a very different way of doing things, however. They were nice enough to let them (mostly) finish AM2R before sending the cease and desist paperwork.