For some reason it hasn't worked in the past. Presumably the combination of strict routers at either end and some problems with the implementation.
There's a bunch of things that can go wrong, but now the messages are much more useful.
Currently I'm running 10.5.6 and taking my Air to a workplace each day. I enabled "Back to my mac" on each end and was pleased to see my home machine - a Mini, show up and be amenable to screen and file sharing while at work.
At home we have an Airport Extreme which is able to do the right port forwarding. In the office whatever they have won't do it, which is fine.