The Screen Names or IDs your are using should belong to the same Service.
That is to say you should be both using an AIM or AIM valid Name (Apple IDs ending in @mac.com or @me.com)
Or to the Jabber Service (various Jabber servers including Google Talk and Facebook's "Chat")
Check the Message Menu > Preferences > Video Section > Bandwidth Limit
This should be at least set at 500kbps.
Can you Video Chat ?
Audio Only and Video Chat uses the same Internet ports through your computer and router.
If you can't Video Chat then you can't Audio Only chat and if you can't do that then the Screen Sharing (An Audio Only Chat+) also will not work.
Follow that with an Internet Speed check
You need to be seeing at least 128kbps as an Upload for Screen Sharing to work.
Higher would be better as at speeds that low you lose some to the "overheads" of maintaining a connection with your ISP and other small now and then checks from the Mail app and any Web Browser that is open.
(This 128kbps figure is Apple's stated minimum.)
With a computer doing nothing else then ichat will grab as much Bandwidth (It's portion of the Internet speed) as it can.
However it is also set up to allow other apps to have priority over the Processor.
This can mean that Time Machine will hold up Video "Production" and also disrupt any incoming Audio and Video.
iChat/Message beta checks the available Internet connection when you start the App.
It writes this info to the com.apple.ichat.plist (even if you are using Messages beta)
If you have the app starting when the computer does the checks the OS is doing may cause the app to think there is less Bandwidth than there actually is.
Following a check by restarting the App it is also worthwhile to check what apps are actually using the Internet.
As stated above, iChat/Messages may in fact be well down the list.
Also other computers and devices on your (or your Buddy's) LAN can also make a difference.
Once you have eliminated all of those possibles then you can try deleting the com.apple.ichat.plist (As it holds the Speed found) and "reset" the .plist
Open the Finder as the "Front" App
Use th Go Menu
Hold the ALT key down to See the Library
Select the Library
Open th Preferences and find com.apple.ichat.plist
Drag this to the Trash ( to delete it)
Restart iChat or Messages beta to recreate the .plist from defaults.
Please, if posting Logs, do not post any Log info after the line "Binary Images for iChat"
iMac 2.5Ghz 5i 2011 (Lion 10.7.2)
G4/1GhzDual MDD (Leopard 10.5.8)
MacBookPro 2Gb (Snow Leopard 10.6.8)
Mac OS X (10.6.8),
"Limit the Logs to the Bits above Binary Images." No, Seriously