[Epic 4G General] mag44:
I had the same issue with my first Epic. I would get the "Cannot update prl ... please call customer support if this issue persists" (Not verbatim but close enough). Phone was basically stock with not rooting or roms, just a few apps from market. All other services worked fine on the phone.

I first called Sprint to get this issue fixed, unfortunately I was in my office multitasking at the time. Working, eating lunch, and trying to talk to the sprint rep all at once was not easy. I phrased my problem wrong telling the lady that "I was unable to download the update my phone" and told her the error message verbatim. She gave me the "There are no upgrades available at the moment for the epic" and said that I shouldn't be able to get an upgrade. I obviously knew that this was not normal, but was unable to explain things further because I had to get to a meeting.

I decided to take the phone to a sprint store that weekend (ended up being three separate stores). The first one was closest to my apartment, I explained the problem. They agreed that this was not normal and said that I should be able to return it to the store I bought it from since it was within the 30 days.

The next stop was the store that I bought it from. After looking at his own epic and the store demo, the rep agreed that this was an issue. He spent a decent amount of time on the phone with some advanced sprint tech support. They recommended some phone reprogramming, this store is not a repair center but luckily there was a sprint repair center across the road. The rep recommended that I take the phone over there and also said that I could exchange it for another if things didn't work out (I didn't have my receipt otherwise I would have exchanged it then).

The rep from the second store wrote down what the advanced phone tech told him over the phone. I took this paper across the street to the sprint repair center and the guy looked at it like it was written in a foreign language! He had no idea what the tech meant.

It was getting close to closing time so he offered to either hold the phone overnight or have me come in first thing in the morning to have them diagnose it.

At this point I decided that that I would just return the phone, however I wanted to call Sprint again as one last resort since the phone was otherwise working fine. This time I phrased my questions more specifically. The phone rep had me power cycle the phone and repeated the "There is no new upgrade for the epic" line that I heard earlier. This time I was able to say that I had tested multiple Epics in three different stores never once receiving this error message. I had to be firm with the rep telling them that I understood that there was no upgrade however this error message is something that shouldn't occur.

Eventually he had me do some reset where I entered my MSL on a "##" menu (don't remember the exact code), the phone re-provisioned itself and everything worked after that. I have since returned the first phone for other reasons and have not had any PRL update issues with my newer epic. The newer build seems to be more solid and the power button seems to have a better response compared to my earlier phone.

TLDR version: Call sprint and have them do a some sort of MSL reset to get the phone re-provisioned. Be firm with the the phone rep, they will insist that there is no upgrade for the phone yet. Tell them that you have used display Epics and this is not supposed to happen.