What version are you using? Wonder if you are uploading the file in the right place.
Old school would be wondering if it is a cache issue. Cron was a good idea, but sometimes I find I have tell the Moodle server to clear cache. I don't think that is the issue.
I have a new 2.6 server with the certificate module and I am getting ready to customize the certificate code. In my 1.9.9 legacy file system at moodle/mod/certificate/pix/signatures, I had a John_Hancock03.jpg In the file system I changed the name to John-Hancock13.jpg. My list was still showing the 03 name. On my computer, I found another file and called it John_Hancock14.jpg . I went to Site Admin>Plugins>Activity Modules>Certificate>Upload. Used the pulldown to select signatures, uploaded my John_Hancock 14 file. It appeared on the list as well as the 03 file.
My theory is that when I upgraded from 1.9.9 to 2.2, along with the new certificate code, they took copies of the ../certificate/pix folders and put them in a super secrete spot that the "new" file system determines. Once done, I probably will not be able to delete them.
Hope this helps you. Your post reminded me I have more work to do before I try the upgrade with all of my server data.