try querying for the rpm that contains libreadline:
rpm -q libreadline
RPM checks for other rpm packages that contain files, not for the files themselves so if you installed the libreadline using some other method than rpm you will have the dependency error. Try installing redcarpet from
www.ximian.com to help aleviate your dependency woahs