I tried kickstarting my iMac and MacBook (both on Lion) and it didn't seem to change anything. I could screen share from work with Back to My Mac, but when I was at home on my own wireless network, I couldn't screen share at all. So irritating. I found this fix, which does seem to work. It involves replacing ARDAgent with an older version, 3.4. This does seem to work, so far. I got the kickstarting ARD instructions from this thread:
https://discussions.apple.com/thread/3289794?start=0&tstart=0
However, these are the instructions for the ARDAgent modification. Thanks, tchaga!
Instructions by tchaga:
1. Download ARD 3.4 (RemoteDesktopClient.dmg) at http://support.apple.com/kb/DL1350, mount it, look inside the package/Contents, copy the Archive.pax.gz to the desktop.
2. Expand the Archive.pax.gz and navigate inside the resulting folder Archive to /System/Library/CoreServices/RemoteManagement
3. Navigate to the same folder at the root of your HD (i.e. HD/System/Library/CoreServices/RemoteManagement)
4. Copy ARDAgent from your HD/System/Library/CoreServices/RemoteManagement to the Desktop and then delete it from the HD/System/Library/CoreServices/RemoteManagement folder (you need admin password).
5. Copy ARDAgent from Archive/System/Library/CoreServices/RemoteManagement to HD/System/Library/CoreServices/RemoteManagement (you need admin password again).
6. Restart