Permissions can be tricky, and if not set and unset correctly can end up with strange bugs; take a look at your database entry for $prefix_user_roles in the $prefix_options table. The data there will be a serialized array; copy the string to a php file somewhere and unserialize it to see if it makes any sense. You should make sure that the 'edit_others_posts' capability is listed under the 'administrator' array.
If it isn't, use php to add it to an array and then reserialize it before you put it back in the database. Just straight editing the serialized string can cause some really bad things.
Also, test all of your plugins. Deactivate them and activate them one at a time to see if one could be your problem. You might want to do this before you change the value in the database, because some plugins will edit that value on (de-)activation.