Up to Maya 4.5, the solution would have been to export the wayward surface as a DXF file and then reimport it. Sadly, with Maya 5 this workflow is no longer possible.
What you can do (and it worked for me), is to use the script I have attatched (written by Paul Anand).
It's called nurbsExtractCurves, and does just that - it extracts a series of curves out of a nurbs surface, either in U or V direction.
After you did this, all you need to do next is to collect these and then loft. Voila!
I applied a Lattice to the new surface and it worked like a charm.
I recommend to create two shelfbuttons, one for every surface direction.
These are the commands you'd need to drag to your shelf:
For curves from U direction:
nurbsExtractCurves -u 1 0
For curves from V direction:
nurbsExtractCurves -v 1 0
NURBS sometimes show this strange behaviour. No idea why - maybe they're getting woozy from their own math.
The DXF route used to help, but...
Subdivide and conquer!
Free your mind, and your ass will follow!