as already stated the smaller the gravel the better it is for all know catfish types.
do you have any d.i.y shops around your end?
to say that you can only find one type of sand seems pretty weird.. try all d.i.y shops for play sand.
cleaning play sand is just like cleaning gravel/ normal sand.. all you have to do is fill the bucket half way with sand, rinse it well (whilst stiring it) roughly 4 times and place it into ur tank... it couldnt get any simpler honestly.
with the size of the gravel you have got.. its a wonder it hasnt happened sooner, i understand how attached you become to catfish.. thats why my 40 was mainly a catfish tank... but if you cant do somthin about ur gravel.. then i wouldnt keep them.
sorry to hear about ur loss