Find out for what years CA is imposing a lien, then file returns for those years showing that you had no CA income & owe no CA tax. Then ask CA to vacate/release the lien. Then click your heels together 3 times & say "but I didn't live in CA".
FYI, when you join the military, you remain a resident of the state you lived in when you joined until you take some positive steps to change residency to another state.