I recently upgraded Emacs and BBDB, and it stopped working to auto-complete addresses in Gnus. The error turned out to be that it was trying to run bbdb-migrate to update the database, and I wasn’t loading that. So I just needed to add this to my .emacs:

(require 'bbdb-migrate)

And do a C-x C-e at the end of that line to execute it. Then the next time I tried to use BBDB by auto-completing an address, it took a few moments to migrate the database, then worked fine.

I’m not sure if I have to leave it enabled, so I just commented out the line for now, and I’ll see if it keeps working after my next restart of Emacs, whenever that might be.