Hi Kevin,
No experience doing this with glmmADMB, but some general comments and a possible solution below.
As you pointed out, the problem of how to deal with prediction and random effects is tricky -- you must choose which RE to include in your prediction, and which are appropriate depends on the nature of the new data. An example of the effects for lme4 predict, using re.form argument, is shown in the 'customized prediction' section of my post here;
http://www.ashander.info/posts/2015/04/D-RUG-mixed-effects-viz/But, as you pointed out, the predict method in glmmADMB can't accommodate random effects.
I think adding draws from your RE distribution to the appropriate rows of your predicted data (on the link scale), given the RE structure, would produce something similar to lme4s predict, but this would take some time to implement!
Perhaps a better, but maybe unsatisfying, alternative is to refit the model using MCMCglmm and use it to predict. I would feel ok about doing so if parameter estimates are similar, possibly computationally painful to fit with MCMC. Some worked examples of models using both packages are here:
https://rpubs.com/bbolker/glmmchapter
Good luck,
Jaime
PS A further resource, if you haven't already seen, is the GLMM faq
http://glmm.wikidot.com/faq but it doesn't seem to have any examples of prediction accounting for RE with glmmadmb.