HD disks could well be the problem. I've had various amounts of luck with them. Some have worked fine, others appear to work, and then develop read errors within minutes, and others refuse to even format.... You really need to find some DS/DD 3.5 floppies....
As for the cleaning disk, any type should work. For Amiga, it should have both the top and bottom read areas open. (Double sided) Almost all cleaning disks are like this. (As almost all drives are, as well. Not many 3.5 single sided drives out there!) I've heard of various techniques to making the Amiga drive spin for the cleaning. Personally, for my A500, I just turned it on, waited for the insert Workbench screen, and inserted the cleaning disk. oooops, it couldn't boot workbench :lol: etc, for a couple minutes.