As far as things go, if Naruto became the Hokage right now, or maybe a little earlier, he'd suffer the same doubts from the others (maybe if he'd become Hokage before the Pain fight for some reason, that's sure to earn him respect).
Gaara and Naruto can draw some pretty big parallels in the way they defended Konoha and Suna, their (Gaara's former) bijuu, their age, their aspirations. I agree that Gaara was placed in the position of power, due to Shukaku. The manga states as much. Now though, I believe all of Suna respect him, for defending them all from a powerful foe, and coming back to life to continue leading them. He has the whole village behind him, the same way Naruto does.
That said; Gaara didn't really have a childhood. The cold, emotionless one he endured, surely caused him to grow up a lot faster than Naruto. They're certainly the future of the ninja world, it'll just take time for the older generation to accept it.
This made me consider the theme of bonds in the series, and how Sasuke was the first one Naruto made. Would it be accurate to say Naruto is the first one Gaara made? Thinking back to how hard Naruto fought to get him back from Deidara, I think I realised just how deep their bond goes. Would Gaara have done the same? Honestly, I think he would have.
I can see the ties between Konoha, Suna and Kumo going very deep in the future.
Yes, Kumo too. I think Kishi's going for a similar thing to the way the Leaf and Sand became close allies again. Start off by having them show apparent hostility, and then have them help each other out.
What about Kiri? Maybe.
...I've started to ramble
