@onykage,
Some guy I know is also working on a package to replace Q3A textures.
From my point of view, you're allright to make your textures from scratch.
Legally, I think it's all okay.
That would be nice if you and him get connected to avoid having 2 texture packs.
It will be up to him, but the texture pack he's working on could be released on a BSD type licence (allowing OA team to GPL-it).
I'll ask him to contact you
