I also had many problems with my Galaxy S4 after the Android 4.3 update. The phone would not stay connected to WiFi consistently. I talked to the Samsung support today and they had me wipe the cache, which appears to have solved the issue.
This can be done:
1. Power off the phone and remove the battery.
2. Replace the battery.
3. Hold down the Volume Up and Home buttons and then hold down the power button to turn on the device.
4. Continue to hold down the Volume up and Home buttons until the recovery menu appears.
5. Use the volume keys to navigate to the wipe cache partition option.
6. Push the home button to select the option.
7. Reboot the device.
This solved the wifi issues with my phone.
The cache wipe has helped battery life issue. WiFi still has issues connecting complaining that the internet connection it finds is too slow or unstable when other devices connect just fine. I have received the same errors when the phone is about the only active wireless device in the house. As a result I have experienced data overages ever since the update to 4.3 which I think that Verizon should refund back to me. I had been happily using my home wireless to avoid my data cap prior to the 4.3 update. Maybe if more complained and asked for overage refunds, Verizon would kick the 4.4 plans into high gear in hopes of burying these issues?
I'm going to hold back in this post, as it is my first here and also the people at VZW are still working to keep me as a customer, with positive things to say about the wireless service they provide. I will be back to post an outcome of how my VZW customer experience goes. I'll just get to the current issues and save my past troubles with the s4 for my impending post(I have much to say).
It's been about a month that I have been with slow or no "LTE" in the central/south valley area (93631). Before, I was able to maintain a solid "4G LTE" signal, out of a 24-hour day I probably get one hour of a 1 bar 4G LTE connection. I called VZW the first representative suggested a new SIM and was confident this would fix my s4, not the case. So they submitted a service ticket for whichever tower it is. I get a e-mail saying the problem with the tower was resolved. I still have the s4 issue. Currently, I'm "waiting it out" until tomorrow to see if the work done to the towers actually solved the issue or the device itself is the "cause". In which case they will try and give me a refurbished replacement. I've been in contact with customer service numerous times over the span of a month trying to resolve this "connectivity issue". At least 3 hours on the phone with CS, 10-15 factory resets, an equal amount of reboots, and without LTE. I've turned the s4 off until tomorrow/ later today, because I'm tired of saving settings/preferences over-and-over.
I made this a reply to, (who4ever), because your course-of-action seemed to have worked out satisfactorily and I may have to go that route.
Thank you all for reading.
Here is a fix that worked for me. Make sure you remove the battery for a couple minutes, I didn't do that the first time and it did not work leaving the battery in. Have not had issues with WIFI bouncing since. For me it wasn't the 4.3 upgrade but some push Samsung did to an application/s as my issues just started occurring in the past 2-3 weeks.
Hope that works for others it did for me.