"add content" suddenly not showing on navigation block anymore
First a clarification about terminology: make sure to correctly separate access to "blocks" from "navigation links": your non admin users seem to have access to that "block" also (that Ajax link in it proofs that to me). Your real issue/question should be something like "why are some of the menu links missing in that block?". 

Seems like you need to resolve that "Access Denied" message first. Even though it's hard to tell (from the screenshots provided), My best guess would be that you need to review/tune some of the settings related to "node" within admin/people/permissions.

So check/confirm that for the users who receive this "Access Denied", they are granted the permission like "View Published Content". If that permission was not granted yet, then do so now and try again to see what happens.

A few more "comments" (moved from the comments below to around here):


The "menu items" that are shown in that block, will be shown (only) to the users who have access to the actual content (node) that the menu items are related to. And apart from that there is the "block visibility", which is typically something you "can" set so that it is only shown (or hidden) on specific pages, or so that it is only shown to users with specific roles.
About "I didn't want every user to other users' published content": looks like there is something you mis-interprete about the "View published content": that permission is ONLY a way to tell Drupal "which roles are allowed to see anything (nodes) that have the "published" checkbox turned on. It seems to me that you MIGHT need to add something like the (great!) "Content_Access" module to implement something similar to what you wrote in one of your last comments.
If it makes sense, you should set the "default" content access for each content type first, so that you only have to change it for those nodes where you want content access to be different from that default. So no need to "go through every content to manage their content access".