Now that the Kyuubi has become buddies with our little Naruto, he shouldn't mind the Toad Sages fusing with his shoulders like before. While Gaara's sand is fast, is it inescapable? We've seen Joki Boy run past waves of sand and actually reach Gaara in one large sprint. Given how fast SM Naruto was portrayed, and with sensory advantages on his side, this should be able to be mimicked.
If this isn't in the desert, Gaara's pretty much screwed since he has the possibility of fighting clones that can throw FRS at Gaara. If he is in the desert, well things are tougher for Naruto. I still think he'd win though, and please bare with me on this. Gaara's automatic sand defense seemed to degrade when it made contact with oil (see Mizukage fight). If Naruto summons a toad that uses oil, than it may very well be the ultimate defense's downfall. If none of this works, than like said before Naruto can have the Sages use Frog Song or barrage Gaara's defenses with Odama Rasengans to truly test its strength. I don't think flight is going to be the major issue here with humongous jumping toads on your side.