I had the same issue on my HTC Rezound after the Ice Cream Sandwhich (ICS) upgrade. Here's how I fixed the issue:
1) Connect phone to computer.
2) On the phone storage and not the SD card, add a directory /media/audio/notifications.
3) Copy the custom notification ringtone to the directory from step 2.
4) On the phone, go to messages. NOTE: Do not go to the settings of the phone and modify the notification tone there. The messages notification sound is separate.
5) Go to Settings > Notifications.
6) Set the "Notification sound"
NOTE: Yes, HTC's ICS should be using the directory /Notifications, but the messages settings doesn't seem to retrieve this information. Only after adding my audio file here did it show up in the list for step 6. However, for normal ringtones, placing them under the /Ringtones directory worked fine without the need to also place them under /media/audio/ringtones.