I just wanted to join in and add that this bug is still present in stretch (and Ubuntu 17.04, as reported here: https://bugs.launchpad.net/ubuntu/+source/seahorse/+bug/1299747).
Keys are generated after a long time, but it is not visible to the user that something is actually happening. This is very annoying and confusing. I guess this is an upstream bug, please forward. Thanks!
signature.asc
Description: OpenPGP digital signature