I would start by checking access for the Account object for the profile. Perhaps, you cloned an existing profile that did not have access to the Account object to begin with. Also, consider your Organization Wide Defaults. Remember that permission sets can only grant access (to a record) not restrict (access to) it. Keep that in mind when assigning it to a user.