I emailed Pajamahadeen Arabic language expert "Ribbity Frog" for his opinion on the interpretation of the Osama video and whether it threatens states that vote for Bush. He responds:

What can I tell you? Even a piss-pot state like Palestine is referred to as "dawlat falestiin" "The State of Palestine". "wilaaya" in the singular is used for a local state, as far as I know. Certainly, Arafat would never refer to it as "wilayat falestiin", particularly since it has the overtones of a local autonomous district subject to a greater empire, and would I think imply a degree of subordination to a greater body. My Arabic dictionary defines it as

"sovereign power, sovereignty; rule, government. administrative distrcit
headed by a vali, vilayet (formerly under the Ottonman Empire); provence (= division of a country, e.g. Tunisia, Algeria); sovereign state (in a federal
union)." etc.

Slipping back into a more demure academic posture, he adds:

The United States is called in Arabic alwilayaat almuttaHida - wilayaat is plural of wilaya, state (the -aat ending is like feminine plural -ot in Hebrew) and muttaHida means united, from root waHad, 'one' (= Hebrew
me'uHadot).

The Arabic "ayy-" is etymologically equivalent to the element "ey-" in Hebrew words such as "eyfo", "eyzo", "eylu" or Biblical "ayyekka" where are you. etc. It means "which", "whatever". Hence "ey + po" (which+here > where), "ey + ze" (which+this > which one).

ayy in Arabic can which which or whatever, hence any or every. ayy wilaaya means "any state" (eyze medina) or "whichever state". The Slate notes the inconsistency in the English translation, but there isn't such a difference really. (Whichsoever state).

I hope this helps.