Well, I was able to contact someone who goes by "Steven A" who has put together this great script called "KTrash". It doesn't use kfmclient, it simply uses mv and some bash scripting to correctly move and (if needed) rename files/dirs, and creates the .trashinfo files that store the deletion date and original location. It works very well! The only problem I have found is that it will happily re-trash files that are already in the trash bin. That shouldn't be a problem most of the time. If you're using it with find (like me), and find runs it on files already in the trash bin, it will re-trash the files, updating the deletion date and changing the original location to "~/.local/share/Trash/...". I've already mailed Steven to see if he can code up a quick fix for it. In the meantime, here's the script for anyone that might want it. It works really well. I think it should be included with KDE itself. :)
Attachment:
KTrash.bz2
Description: BZip2 compressed data