The withdrawal agreement provides a solution. There is quite broad agreement on both sides, and within EU member states in general, about the solution for EU citizens. The problem is that it is linked to the fate of other dimensions of Brexit, and by linking that, once the rest falls apart, this guarantee falls apart unless you use article 50 to still adopt that.
That has to be done quickly, because once the UK is out of the European Union it cannot use article 50. That means that for all the rights set out in that agreement, if they have not been adopted under article 50, you have to go to the different legal basis of the new treaties, which does not give you the same powers. The complete set of rights protected there could never be protected in another way than through article 50, so once the UK is out, if these citizens’ rights have not been guaranteed, it will be too late to provide the same level of protection that we have now. At best, it will come up with a sub-optimal solution that will then have to be ratified in all the member states, so it will also take much more time, which means extra insecurity in the meantime.