Are you using the system id component to check that the hardware and software images are made for the exact same system? It's just an idea, but Quartus could have switched to an opencore evaluation mode when you changed the license. In that case it creates the image in a sof file whose name ends with _time_limited.sof instead of the regular .sof file. You could still be using the old file with a new software image, but the Nios programmer would spot this if you have a system id component.
Another thing to look at is timing. Is the design properly constrained and does it meet timing requirements? If it doesn't, even a slight change could cause the entire system to fail.