The thread that Bill mentioned is: http://www.talkgraphics.com/showthread.php?t=22405

The images there look similar to the sample that you provided, so that could possibly be the source of the problem.

Did you hand trace the shapes or did you use the bitmap tracer?

If you used the bitmap tracer, it's possible that the un-evenness of the trace put a lot of stray nodes in weird placed which might freak out the bevel tool. In that case, I would suggest trying to use the shape editor's smoothing function to clean the shape up a bit, as sunland suggested.