Well, I may have made progress, but I'm not sure. I tried removing the "<ejb-ref>" elements referring to the UIDHighKeyGenerator. That allowed the deployment to complete apparently successfully.
However, when I actually tried to use it, I got the exception that follows this. I checked the "ejb-jar.xml" for the "ejbutils-deploy.jar" and that specifies "RequiresNew" for all the methods of that bean.
Just for fun, I tried adding a transaction specification for this bean in my own application, but that brought me back to my original error of "... not found in this application".
I would ask about this on the "ejbutils-user" list, but there seems to be no activity on that list.
[UIDHighKeyGenerator] Application error: BMT stateless bean UIDHighKeyGenerator
should complete transactions before returning (ejb1.1 spec, 11.6.1)
[UserBean] CONTAINER EXCEPTION:No transaction.
[UserBean] java.lang.IllegalStateException: No transaction.
[UserBean] at org.jboss.tm.TransactionImpl.setRollbackOnly(TransactionImpl.
[UserBean] at org.jboss.ejb.plugins.TxInterceptorCMT.runWithTransactions(Tx
[UserBean] at org.jboss.ejb.plugins.TxInterceptorCMT.invokeHome(TxIntercept
[UserBean] at org.jboss.ejb.plugins.SecurityInterceptor.invokeHome(Security