I set up a Relevant Content Bean and configured a new block that works perfectly for the admin user. I set the permissions "Relevant Content Block: View Bean" to a allow anonymous and authenticated users but the block does not show up for either of those users. If I additionally set the "Relevant Content Block: add Bean" permission then the block appears. If I unset this additional permission again and change back to only have "Relevant Content Block: View Bean" then the block no longer appears for anyone but the admin user.
No special permissions/restrictions are set at the block level.
Note that I've also setup another bean that uses View Reference and the permissions work as expected there.