Device Has been Modified - Updates not available among other problems

[Mickzter97]

So recently when i tried checking for updates for my Galaxy S4, it gives me a message saying that my device has been modified so updates are not available.
I have not rooted my phone.
I have enabled developers options but i turned it off when i tried updating.
Under device status it says Custom.
I've googled how to solve this problem and people suggested unmounting my SD card and restarting. But i don't own an SD card.
Others say go to Android Recovery Mode and Wipe the Cache Partition. I did that but it does not work.

I Have also noticed that when connecting my phone to my PC via USB, loading times are incredibly long. Sometimes it won't even read the phone, or the phone won't say that it is in USB mode.

Also when connecting to Kies, when I do a back up it says there are no messages or apps to back up. Are all these problems related.
Help would be appreciated.

 

[powermzii]

Have you flashed a custom recovery / ROMeven without rooting?

Had the same issue on my N3 when i had flashed a custom recovery but the message went away after i manually flashed a stock ROM