For some mysterious reason no user (even the super admin) can edit his own user profile through the frontend of my site. They used to be able to do this before, but now when a users edits his profile and saves this, he's presented with a logout button and nothing is saved / changed. None of the K2 user fields or even the user password.

I'm not sure when this problem started occurring. Possibly with the upgrade to CommunityBuilder 2.
My setup:
- authors on my site login on the frontend and see the K2 User module.
- They click on 'My Account' where they're presented with the edit fields for their own profile.

- There's also a separate user group on my site that doesn't have access to K2 editing.
- This group can edit their account through Community Builder

You are seeing Joomla!'s native logged in view (logout.php, a simple log out button).
Map the edit user profile into a menu item in order to see all these options.

I've created a menu item which links to Edit Userprofile. The user is presented with the edit fields of his K2 user info. (Like the one in the K2 user module) Submitting the form still results in a page with a logout button, no modules and no changes where saved...

Are you using Joomla!'s and K2's latest versions?
Also is this is a known issue with Community builder (you can check their forums)?

We're running Joomla 2.5.28 and K2 2.6.9 (We're also in the midst of upgrading to Joomla 3, where the problem also occurs)
Couldn't find anything yet on the CB forums.

If you disable CB, does it work properly?

Ah! I've disabled the Community Builder System plugin. Now I can update my profile. So CB is the problem.
I have to figure out what the consequences are for CB when I disable the plugin.

I think you should address this issue to CB.
They might have a solution ready.

I just did. ;-)
www.joomlapolis.com/forum/147-potential-bug/230222-cant-update-k2-user-profile-when-community-builder-system-plugin-enabled

Let us know of the outcome, since other users will benefit too :)