All settings are the default ones. My safety level is set to "safe". The privacy level is the same on all photos and is set to "anyone can see this photo". Similarly the hide photostream from site wide searches parameter is not checked.
I don't think there is any problem with the settings. I just found the following on Flickr's help:
"If your account is new, first you need to upload at least 5 photos. After that minimum has been reached, then it shouldn't take more than a few days until your photos appear in searches, groups, etc. To make sure your photos show in searches, remember to add accurate tags and descriptions."
Whilst the account has been open a while, I didn't start uploading until last night so with any luck they'll start to show up in the public search within a few days.
Thanks for the help anyway.