As far as I can make out, the situation is completely muddy. There are two potential arguments for treating a plan of an Indian tribal government as not subject to Form 5500 requirements. The first would be to argue that a plan of an Indian tribal government is a "governmental" plan.
IRS Announcement 82-146 eliminates the Form 5500 filing obligation with respect to governmental pension plans (which for this purpose would include 401(k) plans). The second would be to argue that Indian tribal governments are normally exempt from all regulations not specifically intended to apply to them.
As to the first argument, Internal Revenue Code ("Code") section 414(d) and ERISA section 3(32) define a governmental plan as a "plan established and maintained for its employees by the Government of the United States, by the government of any State or political subdivision thereof, or by any agency or instrumentality of any of the foregoing." Code section 7701(a)(10) includes the District of Columbia as a State, but does not mention Indian tribal governments. Code section 7871 treats Indian tribal governments as states for certain purposes, including for purposes of maintaining section 403(B) annuities. However, it does not list 401(a), 414(d), or 6047 (the section imposing Form 5500 requirements) as being among the Code sections for purposes of which an Indian tribal government is considered a state government.
As to the second argument, PBGC Opinion Letter 81-3 holds that a corporate council of elected governmental officials of several Indian tribes that was established to coordinate the distribution on Indian reservations of federal (and, to some degree, state and private charitable) funds is exempt from ERISA. The basis for this determination was not specifically that the plan was a "governmental plan," but that "while the exercise by Indian tribes of their powers as sovereign nations is subject to limitation by action of Congress, legislation will not be presumed to limit tribal sovereignty in the absence of specific language stating that intent." By contrast,
Smart v. State Farm Insurance Company, 10 E.B.C. 2060 (7th Cir. 1989) applied ERISA to a group insurance plan maintained by an Indian tribe for employees of a tribal health center. And even the PBGC, in Opinion Letter 89-9, held that a defined benefit plan maintained by a factory owned by an Indian tribal government was not exempt from ERISA where the factory was "an off-reservation operation, most of whose employees, and all of whose customers, are non-Indian."
And apparently, even Congress does not know the answer to this one. The Conference Report on the Small Business Protection Act states with respect to the provision permitting Indian tribal governments to maintain 401(k) plans that "no inference is intended with respect to whether Indian tribal governments are permitted to maintain qualified cash or deferred arrangements under present law." The only reason that Indian tribes would have been prohibited from having 401(k) plans before the SBJPA would be if they were treated as state governments. (An Indian tribal government would not be an organization "exempt from tax under this subtitle" within the meaning of Code section 401(k)(4)(B)(i), because its tax exemption derives from sources outside of the Code.)
Thus, Congress apparently decided to resolve the immediate issue of whether Indian tribal governments could have 401(k) plans without expressing an opinion on whether they should otherwise be considered "governmental" for purposes of the Code and ERISA. And that omission has all sorts of consequences, even beyond the Form 5500 filing requirement--
e.g., whether plans of Indian tribal governments are exempt from Title I of ERISA, or from the various Code provisions from which governmental plans are exempted.
I don't know whether any of this helps, but at least you are not alone in being confused.