I made some progress on this after chatting live with Eric from Digi support, and also reading around HOWTOs on the net.
First point is that the XBee 2.5 model is discontinued and no longer supported by Digi, even though it's still pretty widely sold. Eric mentioned that there are some better and more up-to-date models available, I think the 'ZB' line rather than the 'ZNet' is what you want. But I'm not completely clear on that yet (and I have the 2.5 which I wanted to get working).
Next, because the XBee 2.5 and XBee PRO 2.5 are no longer supported, the firmware is not available automatically from the X-CTU program. To get the firmware, you can still download it manually, and then use the 'File' option in the X-CTU download tool to get X-CTU to use the latest firmware. The firmware I needed was on this page: http://www.digi.com/support/productdetl.jsp?pid=3261&osvid=0&s=269&tp=2&tp2=0
Next, you can follow the information in the 'Xbee Configuration guide', see link at http://www.arduino.cc/en/Guide/ArduinoXbeeShield
You have to set up one XBee as 'ZNET 2.5 COMMUNICATOR AT' (the 'home base' xbee) and the other as 'ZNET 2.5 ROUTER/ENDPOINT AT' (the 'remote' xbee). You can assign names (ID) and network IDs (PAN ID) to both XBees using X-CTU.
Using this approach, the serial test worked OK, so it's looking good. According to Eric, what one should really be doing here is upgrading the firmware to the new 'ZB' feature set, for which instructions are here:
http://ftp1.digi.com/support/documentation/upgradingfromznettozb.pdf
I'm entirely sure why one should do that, other than to enable digi to support you better, because they don't actually support the ZNet modules, which apparently date from year 2006.
Best Answer
I think what I am missing is that the XBee's modules must be programmed both to send and to receive data. In the following thread there is someone claiming that acomplished that and posting some code which will run in a ATMega processor:
http://www.arduino.cc/cgi-bin/yabb2/YaBB.pl?num=1223492621/all
I also found a tutorial of how to configure the XBee module using a graphical environment:
http://forums.trossenrobotics.com/tutorials/how-to-diy-128/xbee-basics-3259/
From what I read above, I tested it, and I finally established a connection, then I wrote a tutorial showing how I did it.
http://arduinolessons.blogspot.com/2010/10/how-to-use-xbee-module.html
Unfortunately not all data gets through though...
Since I'm using a XB24-B the following blog gave me some light:
http://lizard43.blogspot.com/2009/04/xbee-series-2-jv-channel-verification.html