"I also pray to the one and the only Almighty Allah to teach a telling lesson to Bush, Musharraf and their forces, and give a chance to the lions of Islam to kill the slave of Bush in Pakistan," reads the leaflet.
Musharraf has survived several al-Qaeda assassination attempts by Pakistani jihadi groups since siding with the US in a global "war on terrorism" following the 9/11 attacks on the US.
And bin Laden's Egyptian deputy Ayman al-Zawahri, who is believed to be moving between the Pashtun tribal lands on either side of the Pakistan-Afghan border, had last month issued a videotape again calling for Pakistanis to overthrow Musharraf.
Printed in Urdu, the leaflet began with an introduction in Arabic saying that it was a message from bin Laden calling on Muslims everywhere to aid the tribes people under attack from Pakistani forces in Waziristan.
Its signoff read "Mujahideen Emirates Islamia Afghanistan", or the Holy Warriors of Islamic Emirates of Afghanistan.
The leaflet was circulated in Miranshah and Mir Ali, two towns in North Waziristan, where clashes between pro-Taliban militant tribesmen and security forces have worsened since early March after helicopter gun ships smashed a compound used by fighters, mostly from Chechnya, Central Asia and Afghanistan.
There has been a lull in fighting for the past few days, and an unofficial truce is expected to hold through to the middle of next week as thousands of Muslim preachers and scholars have converged on Miranshah to hold a congregation over several days.
Musharraf has survived many
al-Qaeda assassination attempts
The congregation was organised by Tablighi Jamaat - a largely apolitical Lahore-based missionary group whose followers spread Islam throughout the world - and its main event passed off without incident on Saturday.
Bin Laden is believed to have passed through North Waziristan during his flight from Afghanistan in late 2001, but most security analysts believe that while he is probably somewhere in Pakistan he is unlikely to be in the tribal areas.
Military officials say they have killed 324 Muslim fighters in North Waziristan and lost 56 soldiers since the middle of last year.
A Pakistani intelligence officer told Reuters last week there were up to 1,000 foreign militants still roaming around North Waziristan.
The military campaign switched to North Waziristan last year from South Waziristan.
Embarrassingly for the Pakistani authorities, self-avowed former Taliban fighters are now imposing their law in large parts of South Waziristan and recruiting fighters to sneak across the border to wage a guerrilla war against US-led and government forces in Afghanistan.
US: Bin Laden in Pakistan
Meanwhile, the US ambassador in charge of counter-terrorism said on Saturday that parts of Pakistan are a “safe haven” for militants and that Osama bin Laden was more likely to be hiding there than in Afghanistan.
Ambassador Henry Crumpton lauded Pakistan for arresting "hundreds and hundreds" of al-Qaeda figures, but said that it needed to do more.
Crumpton says parts of Pakistan
are safe haven for militants
"Has Pakistan done enough? I think the answer is no. I have conveyed that to them, other US officials have conveyed that to them," he told reporters at the US Embassy in Kabul after talks with Afghan officials.
Maj Gen Shaukat Sultan, the chief spokesman for Pakistan's army, dismissed Crumpton's assertion that Pakistan was not doing enough.
"It is totally absurd," he said. "No one has conveyed this thing to Pakistan, and if someone claims so, it is absurd."
Al-Qaeda leader captured
Crumpton confirmed that Pakistan had captured Mustafa Setmarian Nasar, a top al-Qaeda strategist with a $5 million bounty on his head - whom US and Pakistani officials say was arrested in the south western Pakistani city of Quetta in November.
"If we knew exactly where bin Laden was, we'd go get him," Crumpton said. "But we're very confident he's along the Pakistan-Afghan border somewhere...there was a "higher probability" that bin Laden was hiding on the Pakistan side
US ambassador in charge of counter-terrorism
Crumpton said that this showed that Pakistan was working to arrest al-Qaeda leaders.
Pakistan has also launched repeated counter-terrorism operations in its lawless tribal regions close to the Afghan border over the past two years, in which hundreds of militants and soldiers have died.
"Our expectation is that they will continue to make progress, and we know that it's difficult," he said. Pakistan "can't remain a safe haven for enemy forces, and right now parts of Pakistan are indeed that."
Crumpton said US officials continued to believe that al-Qaeda leader bin Laden was somewhere along the Afghan-Pakistani border, and more likely on the Pakistani side.
"If we knew exactly where bin Laden was, we'd go get him," Crumpton said.
"But we're very confident he's along the Pakistan-Afghan border somewhere," he said,adding that there was a "higher probability" that bin Laden was hiding on the Pakistan side.