Sorry to jump in on this thread, but I too am in a similar position. I have the Desire which I got when they first came out. Great phone (at the time) but I'm a bit disappointed with the available memory, even after rooting with SURoots Rom.
The Galaxy s II seems streets ahead of the Desire in all departments so I'm really tempted and will be going the the Carphonewarehouse tomorrow to have a bit haggle.
Can I ask, will the 16Gb version be enough for me or should I go for the 32Gb version. The reason I ask is that I don't want to be caught out like I was with the Desire last year. I thought it was enough at the time but 6 month later found out it wasn't. Is the 32Gb version able to use all/most of its built in memory for apps or is it just storage space.