Det är oklart vem som stoppade landningen men en källa nära president Ashraf Ghani berättade för BBC att återkomsten inte hade samordnats med regeringen.
Gen Dostum reste till Turkiet i maj mitt bland hävdar att han beordrade sina män att kidnappa, slå och våldta en politisk rival.
Han förnekar ett orätt handlingssätt. Hans talesman sa att han gick för en läkarundersökning.
Atta Mohammad Noor, den mäktiga guvernören i norra Balkhprovinsen, väntade på Mazar-e Sharif flygplats för att träffa Gen Dostum på måndag kväll, rapporterade Pajhwok nyhetsbyrån.
Mer än 1.000 personer följde guvernören för att ta emot den tidigare krigsherren på flygplatsen, som är nära hans hemprovinsen av Jowzjan.
Vittnen sade att några Dostum-anhängare hade affischer med slagord som "Välkommen tillbaka till vår kära ledare", rapporterade nyhetsbyrån Reuters.
Men planet avleds till Ashgabat i Turkmenistan.
Tidiga rapporter tydde på att tyska styrkor låg bakom flytten. Men Nato förnekade senare detta och sade att sådana beslut var en fråga för de afghanska myndigheterna.
En källa nära president Ghani berättade för BBC: s afghanska tjänst att Gen Dostums beslut att återvända utan att rådfråga myndigheterna i Kabul hade orsakat misstankar.
"Vi ville att han skulle komma till Kabul... eftersom vi ville ha en tydlig förståelse för vad som händer", sade källan.
"Det finns inga rättsliga hinder för honom att återvända, regeringen har inga problem, men han måste ta rätt väg."
Gen Dostum, Atta Mohammad och Mohammad Mohaqeq, en annan inflytelserik etnisk ledare, bildade nyligen en oppositionsgrupp som krävde stora politiska reformer. De vill begränsa presidentens makt, som de anklagar för att ackumulera makt.
Gen Dostums tjänstemän har förnekat att han var på planet som avvisades.
Men en av de män som hade till uppgift att förbereda för hans återkomst bekräftade till BBC att Gen Dostum hade talat med sina män från Ankara på måndag morgon. Han hade instruerat dem att samordna med Atta Mohammad och Mohammad Mohaqeq och att organisera ett större evenemang för att lansera den nya koalitionen.
Vicepresidenten är en före detta krigsherre med decenniers erfarenhet av Afghanistans turbulenta politiska arena.
Han har fått skulden för några av de värsta illdåden i landets långvariga inbördeskrig, men anslöt sig till landets nationella enhetsregering 2014.
Anklagelserna mot honom kommer från Ahmad Eshchi, en före detta allierad, som säger att han led dagar av svår misshandel och sexuella övergrepp på Gen Dostums befallning.
Han sa att vicepresidenten och tio andra män misshandlade honom medan han tvångsmässigt hölls i Gen Dostums residens i november 2016.
Före detta krigsherren förnekar anspråken och har sagt att Eshchi fängslades av landets underrättelsetjänst.
Under 2008 reste Gen Dostum till Turkiet bland liknande anklagelser om att hans personliga milis hade kidnappat, misshandlat och sexuellt angripit en politisk rival i Kabul, och sedan sköt på polisen som reagerade på incidenten.
Afghansk vice ordförande Abdul Rashid Dostum försökte flyga tillbaka från Turkiet sent på måndagen men nekades tillstånd att landa, säger tjänstemän.