Permission denied
Double check that you have root access and that any superuser permissions app you have lets Barnacle get root. If you have Terminal Emulator or adb (get it with the Android SDK), open it (adb shell). Then type in the command:
su -c id
If the output does not start with uid=0(root)... then you don't have root access.
All I see is "Starting..."
Barnacle is waiting for the ConnectivityService to announce that your mobile data network is connected. You might be in an area of poor coverage.
Barnacle will also wait until WifiManager is disabled. Sometimes, wifi will get stuck in an "error" state. To unstuck it, simply enable and disable wifi.
Could not bind to DHCP port: Address already in use
This is probably not a critical error: a server is running but out of control of the app, so you won't get notification when a client connects. Make sure you are not running any other tethering app, and simply try "Start" again.
A reboot might be necessary. Turn your phone off and on, or simply run
adb reboot
NAT restart: Message too long
On Samsung Vibrant the MTU of the mobile data interface is set to 1280. Since version 0.5.2, Barnacle will send ICMP packets to the client to indicate that the MTU needs to be reduced.
It does not report errors but my laptop can't connect
First, check the wiki and,
if the Supplicant working column says "no", then make sure you have set
Generally, establishing ad-hoc connectivity is a bit tricky. See FAQ for more information.
Could not connect to NAT
This is just a warning. When a client connects, the UI will try to connect to NAT again. This connection is only necessary to perform Access Control and Port Forwarding.
None of the above
I haven't encountered your error yet, but you could help out by following the debugging guide.