I'd do three things. First, I'd get the right XBees. If you want two XBees to talk to each other, and only two XBees, you want point-to-point models, not mesh-network models.
Second, I'd get a USB explorer to program the XBees with.
Third, I'd use X-CTU, rather than putty, to configure them. X-CTU is distributed by digi.com (for Windows only, which is its only drawback) expressly for programming XBees. It provides a lot more information about any failure to communicate with the XBee.
Alright, but is it really not possible to do it with the wireless shield ?
I'll get an USB explorer
were you able to succesfully do a write with "always update firmware" checked?