The steps to reproduce are:

1) Create a search (Click on search in the left hand
menu, enter your criteria and a name, click search).
The exact criteria for the search does not appear to
matter.

2) Click on the 'edit' hyperlink next to 'Your Queries'
to bring up a
list of your queries.

3) For the query that has just been created, change the
'Private to you?' field to 'no' and click Save Selection.

4) The query now becomes public, but it is no longer
possible for you (or from what I can tell any other
user) to edit it. Under the edit heading is the text
'[not yours to edit]'.

Logged In: YES 
user_id=707416

I think this is fixed isn't it Richard? At least I get
an edit link for public queries.

Logged In: YES 
user_id=6405

Indeed, this appears to be a dupe. CHANGES notes for 1.0:  
  
- enable editing of public queries (sf bug 966144)