I started getting that last Monday night (I'm on EDGE--no 3G around here). It's been pretty intermittent since then, though. Sometimes Safari works well, at other times, it pretty much stops completely, regardless of the number of bars I have showing.
This afternoon, Safari worked perfectly, and very fast. This morning--in a different part of the city--I got one web page to load, then nothing came up and I kept getting that message.
I'm about to call AT&T to see if it's a local network thing or an iPhone thing.