General :: Changing File Permissions Works As Root But Not As Sudo

I have a really strange problem. I have a few files in a large directory that I want to make readable by everyone. So I try this:

sudo find readme* -not -perm -o+r -exec chmod +r {} ;

and get this:

sudo: unable to execute /usr/bin/find: Success

I don't know why it says Success, because the permissions were not changed. I verified by typing this:

find readme* -not -perm -o+r -exec ls -l {} ;

and get something like

-rw------- 1 root root 536871076 Nov 22 14:06 readme_20101122200429
-rw------- 1 root root 536871892 Nov 22 14:08 readme_20101122200642
-rw------- 1 root root 293458128 Nov 22 14:10 readme_20101122200859

as a last resort, I tried:

sudo chmod +r *

and got:

sudo: unable to execute /bin/chmod: Success

and again Success really means fail. So, I gave up and logged in as root and tried:

find readme* -not -perm -o+r -exec chmod +r {} ;

This time it worked. Why?

EDIT: /etc/sudoers looks like:

## Allow root to run any commands anywhere
root ALL=(ALL) ALL
##Me
user1 ALL=(ALL) ALL