I was in Barcelona as well...I could see the Vodafone and Movistar networks, and when I'd select either one to connect...it would crunch for a bit and then say it could not connect. The fact that it picked up these networks leads me to believe it's picking up the various frequencies just fine; the problem is the phone is not "interpreting" them properly for use.
There's a $3.99 monthly charge on my bill for int'l roaming, so I assume that should allow me to get service. (I had the same thing happen to me as jg70124 -- the clowns at Cingular didn't activate the right feature.)
If any of you could be so kind...if you go into Preferences > Network (under Communications) > Connection (second line item), do you see GPRS? Or GSM? I believe, in order to work in Europe, it must be GSM. And I can't get that to appear on my Palm.