Back to my Mac was sketchy with 10.5.0 - in fact it barely worked.
10.5.1 seemed to fix that. So make sure you've done a software update.
Then, make sure Back to my Mac is set to 'On' under the .Mac pane of System Preferences. Also, click Sharing Preferences while you're in there to ensure that screen and file sharing are both selected.
This should be done on both machines. And of course, both machines need to be on so make sure any energy savings preferences are set to Anti-Kyoto.
If you still have issues, I don't know what to tell you. If you are trying from a Starbucks or something it's possible that they're blocking some sort of port maybe?
Who even knows? Perhaps Santa Claus, Hanukkah Harry or Kwanzaa Steve.