It can be solved, and the programming part is not that difficult, what's more difficult is having the users actually do the swap as they will have to do it manually.
On your old token contract you have the balances of your token holders. Say:
Contract OLD_TOKEN: balances[0X_USER_A] = 1000;
You will want to have this now:
Contract OLD_TOKEN: balances[0X_USER_A] = 0;
Contract NEW_TOKEN: balances[0X_USER_A] = 1000;
For this to happen, you would have to code the NEW_TOKEN contract so it can be paid with OLD_TOKEN and give 0X_USER_A that balance.
The way that would have to be done is having the user call approve on his OLD_TOKEN, granting your NEW_TOKEN an allowance of the old tokens.
Once your new contract has said allowance, you or each of your users would have to call a function of NEW_TOKEN that transfers the old balance to the new contract and then mints / assigns a balance of NEW_TOKEN to the user.
So, basically, what this NEW_TOKEN contract would do is use the OLD_TOKENs of your user to pay for tokens this NEW_TOKEN contract has. But for it to be able to do that, first the user has to approve the new contract to use his tokens.
As far as I can tell, this is the only way to do it, which has a suboptimal user experience as your users would have to manually approve on the old token and then call another function on your new token to redeem the tokens.