yeah I have seen this before but it usually has to do with the geometry. If you attempt to bevel an edge that is to close to another edge the bevel will appear not to happen because it is laid right on top of the edge you selected.

Can you post a screen shot of the geometry and all the edges you are trying to bevel when the bevel appears to fail?