I recently registered on heroku with my work email address : peter@fitzgibbons.info (obsfuscated)
My ssh id_dsa though is signed with my personal email address : peter.fitzgibbons@gmail.com.

Heroku doesn’t like this one bit.
Following this advice, I created id_heroku_rsa wtih my work-email comment.

Still no-joy.  But, this StackOverflow thread left a clue… using the ssh debugging output, I can see that ssh is still trying to send id_rsa or id_dsa.
The answer, included on that post is to ‘ssh-add’ the special key created.

Voila, now my push succeeds.