Hi, there! I had this error, too, and I think I might know what it is. You mentioned that all users already have nicenames. What link structure are you using? Try switching permalinks to “None” (the default) and seeing if the profiles work. If they do, then that means that you need to manually edit your users’ nicenames in the WordPress database. The nicenames must match the display usernames of the users.
An alternative solution is to use 301 redirects in your .htaccess to redirect profile links. The profiles of those users whose profiles are broken actually do exist. Try replacing the part of the URL that contains their username with their user_nicename. You may find that they exist, so you can do redirection if you’re afraid of messing with the mySQL. This is definitely the inferior solution, though. Editing the nicenames in the mySQL shouldn’t cause problems.
