When I went to discover Muiquun, it shows I have storage available there now, however using a Maid there's no ability to use it.
"You can access storage in other regions by completing the [Abyss One] main questline"
Which I did already... seems like a bug? Although with no negative karma it's not like I can interact with any NPC there.
That's correct, it's a red player town.
A quest line was added so that you can get Muiquun NPC knowledge etc. without being red. But the storage is only for red.