Are permissions working elsewhere as expected in the site? Are users able to edit the contents of the library or only view the items? To me it sounds like it could be one of two things:
1. a web application user policy could be used to grant all users read or full control access.
2. when you created the new library and broke permission inheritance, you didn't remove the permissions you don't want (i.e. all users accessing the library)
My Sites need to be in a content source for them to be crawled. As well, SharePoint needs to run an incremental or full crawl on the content before an item appears in search results.
I would start by looking at search to see if the crawls are working, My Sites are crawled, and look at the crawl schedule to see when crawls run to figure out when you should expect new items to be searchable.