"The responsibility for the current situation in Saudi Arabia rests with the regime," said the voice on the tape, broadcast on one of the principle Islamist Internet sites and subsequently on Aljazeera.
The authenticity of the tape could not be immediately verified, but analysts it sounded similar to other tapes attributed to bin Laden.
"In Saudi Arabia, it is the king and not Allah who commands sovereignty and complete obedience," the voice said. "I advised the government two decades ago to remedy the situation ... but it has not changed at all."
'Who will catch Osama, and where?'
"We pray to Allah to welcome the souls of the mujahidin (Islamic fighters) who attacked the American consulate in Jeddah," he said, in an obvious reference to the December 6 suicide attack in which 12 people, including four attackers, were killed.
"We are not talking about a corrupt, impious leader, but about the apostasy and collaboration of leaders with the infidels.
"Since there is no difference between [Paul] Bremer, the former governor in Baghdad, and [Iyad] Allawi, the current leader, in applying US policies in Iraq, there is no difference between Bremer and the rest of the region's leaders in applying US policies," it said.
Addressing "Muslims in Saudi Arabia in particular and in other countries in general", it said: "This is a message about the conflict between the leaders of Riyadh and people of the country and the way to solve it."
"The necessity of security and safety, the sanctity of Muslims' blood, the necessity of harmony and union and the dangers of conflicts and separation (division) have been discussed a great deal in Saudi Arabia.
"They have claimed that the mujahideen are responsible for the continuing incidents in Saudi Arabia. But it is very clear that it is the government's responsibility as it has ignored all conditions required to ensure safety and prevent bloodshed."
"If we want to correctly, practically and scientifically solve the conflict, we should know its reality, roots and directions. Part of this conflict is internal, but in other dimensions it is a conflict between international non-believers supported by the US-led apostates on the one side, and the Muslim nation and the mujahideen brigades on the other side," Aljazeera quoted from the tape.
America's war on terror: Complete Coverage
More from rediff