Interestingly, it is possible to learn to walk when you never had a vestibular system, although the gait is visibly distorted and when you know what you are looking for you can easily spot it. Those who suffer from CHARGE, and are left able to walk, can still do so despite sometimes entirely missing their vestibular system. But learning to walk with a vestibular system and then losing it later seems to be very, very difficult to recover from, if it is possible at all.

Can humans with issues in the optical stream use the gyros? I find it harder to balance with my eyes closed, though obviously not impossible.

Well, the blind and sight-impaired have been walking (and running) for years, so I'd vote "yes".

Even people with impressive visual hallucinations are still capable of walking.

That said, vertigo (where your eyes and your inner ear are in violent disagreement as to whether you are moving) can impair movement, though you can grow accustomed to the "disagreement".

I think the optical stream fits more of an error correction/secondary data stream in this case.

The difficulty may be down to you trying to use other senses and overcompensating on the data (e.g. air pressure, which tells you something is near-ish you but not if it's about to contact you so you react)