What are solutions to the "Unexpected error while attempting to bind. Operation cancelled." message when trying to bind

Not much detail to go on, there. The following might or might not be things you've already checked...

• How was local DNS services and networking confirmed?
• What is the OS X versions?
• Do other clients bind, or is this a new environment?
• What's the general local network look like? (How simple or how complex is this?)
• Using all Open Directory through, or is Microsoft Active Directory involved here?
• Check the console logs in the client and in the server for any relevant details that might be listed there.
• Are there any references to DNS servers other than that operating on your OS X Server or whatever local DNS server is providing your local DNS? With the typical NAT'd network, that must be DNS server(s) located on your local network.

Has this worked before, or is this a new configuration?

On the server, launch Terminal.app from Applications > Utilities and post the output of the following harmless diagnostic command — and you'll need to enter an administrative password when requested:

sudo changeip -checkhostname

On the OS X (presumably) Mavericks client, please post the IP address(es) of the DNS server(s) you're referencing. These are available via the System Preferences > Network > Advanced > DNS settings.

To check the console logs, launch Console.app from Applications > Utilities on both the client and the server, and then attempt the binding, and then post a (short! no more than ~25 to 50 lines!) of any errors related to the binding error.

If you're not in a position to post configuration details here — which is perfectly reasonable, and entirely your prerogative — or if I'm getting too confusing or too technical with some of the questions here, which would be my error of course — then (assuming these systems are under warranty) I'd suggest contacting the folks at the local Apple Store and having a chat with the local Geniuses about this, or checking directly with the Apple Support folks via telephone.