EDIT: The solution ended up being simply rebooting the iPhone as discussed in the comments below.
Unfortunately, an iPhone with Locate for iBeacon (or similar iBeacon apps) is not a very good troubleshooting tool for testing whether your Raspberry Pi is transmitting. It will only give you a confirmation if absolutely everything is working perfectly with a full UUID match.
It sounds like you have done your homework on making sure the advertisement configuration is not malformed. The next possibility is that your Raspberry Pi is not transmitting advertisements at all.
You need to verify that your Raspberry Pi is actually transmitting any advertisements with your BLE dongle. Lots of things could make this fail including the BLE stick hardware, BlueZ configuration, etc. There are some Bluetooth LE scanning apps for iOS (none free, unfortunately) that might tell you if your unit is transmitting advertisements at all, but iOS does not let you see the raw bytes of the transmission so these apps can't tell you if the advertisement is malformed.
There are also apps that can do this for OSX, Android, and Linux. (Heck, if you have a second Raspberry Pi, you can just enter the command sudo hcitool lescan --duplicates
to see all advertisements.)
Finally, one quick thing you can try to make sure your bluetooth stick isn't in a bad state is to issue the folowing before the other commands:
hciconfig hci0 reset
If you get totally stuck, Radius Networks can ship you a SD card with known working software for $20. Or a full assembly for $100. You can get a Bluetooth dongle that is known to work here.
Full disclosure: I am Chief Engineer at Radius Networks.