I started having the exact same issue today with My Galaxy S4 as well. After reading your post, I think I might excgabge it for an HTC One instead.
Same problem here, worked fine yesterday. Today I get Wi-Fi calling registration failed. I've turned it off then on. Restarted the phone after a battery pull. Everything I can think of, no luck.
It has nothing to do with location since all of these people have said it was working from their location till recently. Mine for instance, worked perfectly on several networks, home, work and public until 2 days ago. I have location services enabled I have cleared the cache for Google play services and Google Services Framework, I have enabled and disabled it many times, I have updated profile and PRL many times, disconnected and connected to WIFI many times, rebooted the phone many times, any other hopeless ideas ? To add to the misery, since this has occurred ALL calls have extremely poor audio quality, sounds as if the other person is in a bucket and the caller/receiver says the same about the quality they are hearing, WIFI calling on or off. Great idea Sprint...EPIC FALURE !!!
I just got off the phone with Customer Service. They removed WIFI calling from my account and re-added it. After hanging up I entered ##873283# and updated PRL and Profile. At this point the App asked for permissions and you have to accept and enter your name, the phone will go thru the setup process for WIFI calling. This all worked OK. I still have an error the service is on would you like to register your location ? I have registered the location many times, same error message ! However now when I go to the phone keypad the CALL button is the WIFI calling call button not the standard call button. It appears this method has fixed the issue but not the error messages people are getting. I called Customer Service back and had them remove WIFI calling and re-add it after I hung up, while I was on the phone I was disconnected immediately, indicating that I was indeed calling via WFI calling. At this point I did ##873283# once again and updated the PRL and Profile. I believe for the time being this is the solution.
Update: after letting the phone sit for several minutes after this procedure it appears the service working correctly no error messages....
I have had the same problem as of yesterday. Today I did this and it fixed the issue. I did all the previous troubleshooting found in the threads and none of that worked. My wi-fi calling is in my plan description. It's been working fine for the past three weeks until yesterday. I turned off the normal wi-fi on my phone, Note 3, and then let it sit with the wi-fi calling enabled to see if I would get the "registration failed" error again after clearing the initial error. After a minute or two, a screen opened to enable wi-fi calling and then click "ok" to enable. That worked and everything is back to normal.