The NATF program probably would have worked out fine, albeit expensively. There has always been speculation that part of the selection of the F-22 over the F-23 was because the F-22 was considered more suitable for a navalized version - and the comparatively small design differences between the F-35A and F-35C designed later by the same group suggest that a similar amount of work would have been involved in navalizing the F-22. Coatings would have been an issue in the 90s, but would largely have been solved by an realistic service entry date in the late 2000s. What killed the NATF was post-cold war budget reductions and shortsighted policymakers, not technical challenges.
The story of a navalized AH-64 is an equally strange saga. To hear the USN and USMC tell it, you would think it impossible to operate the AH-64 from a ship, yet the RN has done so extensively with relatively minimal modifications to the airframe. Given the small production run of the AH-1Z/UH-1Y program, it's questionable if much was saved. Certainly if you look at foreign customers, the capability/price of the AH-64 has been much more appealing than the AH-1Z.