Sounds a lot like Phantasy Star Online: Episodes 1 and 2 for GameCube, but that ain't it.

But that game does sound interesting, please tell me once you find out what it is.