I don't know why it is failing with Required, but you always want to use Requires New. The reason it you always want the number to increment, even if the transaction rolls back.
Also, there is a locking issue. With Required the auto number bean will be locked until the end of the transaction. This means that your application can only create new beans in a single threaded mode (very slow).