[lebaigneur]

Thanks, I deleted nextgen and everything got back to normal for all users.
Except for one user, he had an underscore in its nicename, I had to change it to an hyphen in the DB for him to have a working edit profile link.

[lebaigneur]

For anyone interested, there might be solutions for you here:
https://buddypress.org/support/topic/user-cant-edit-profile-page/
A possible fix in a pastebin link, a possible link to Nextgen plugin misbehaving.

Turning off/deleting nextgen did it for me, for 99% of my users.
I still had issues with one of my user, the nicename had an underscore character in it where all the other had a hyphen. When I changed the underscore to an hyphen directly in the DB, it fixed it for this user too.

Hope it helps.