I've also tried delineating watersheds in New Mexico without success. The only part of NM where delineation gives results is in the Canadian river basin.
This is a known issue in the EPA Delineation tool - the EPA Delineation web service doesn't have the streams in New Mexico Rio Grande basin connected to the NHD+ network.
The change I made in HydroDesktop 1.4.10 is now correctly displaying the actual error message returned by the server: "The selected flowline (stream segment) is not connected to the NHDPlus stream network". instead of the user-unfriendly error.
I've contacted the EPA Waters team and asked them what is the schedule for supporting new Mexico.