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 Skip wpa_supplicant in Barnacle's Settings (access via the menu button) as below:

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.