you have two options:
1) Make your new column a Site Column, then it will appear in the CQWP filter dropdowns (easiest and I think the best way)
2) Export the CQWP and modify the .webpart file (to much work, but it will give you even more control of the result)