I copied this from one of Jennewts posts as she says it so much better than I can (I'd probably confuse you!) "Cycling is the process where you get the tank ready by keeping a fish in it to get the tank to the point where it breaks down waste products naturally". See:
http://www.caudata.org/cc/articles/cyclingEDK.shtml
http://www.caudata.org/cc/faq/FAQwat.shtml
By doing a complete tank clean you wiped out your good bacteria on your established cycled tank and rocks and it has started cycling from scratch.
You will need to test your water (most petshops will do for free) until you can get a test kit set, especially while it is cycling.
The new cycling could have caused the gills to burn down too (from toxic ammonia and/or nitrite as the wastes decomposes). And doing only a weekly waterchange during this process won't remove enuf of it make it safe. Ideally 25% waterchanges every few days (you can gauge when you need to do a water change by testing every 2nd to 3rd day, if the ammonia and nitrite are high do a 25% waterchange then.
The worms may have been there because of excess waste - any uneaten and decaying food/waste (which could be stuck under gravel/rocks buried in sand, under decos, in between plants or caves). The turkey baster works great in these areas (saves pulling out the siphon/gravel vacuum each day.
Also how big are your rocks are they the river rocks?
Do you feed those tubifex cubes? Our 3yr olds were fed solely on those (as previous owner was too busy to vary their diet and they were easy, hence his reason for sale), but the first week or so we had them their poos were really nasty (a sort of stringy white stuff and made the temporary tank smell even tho we did complete waterchanges - while theirs was cycling). Ours loves earthworms (no need to dig for them) lift up potplants, piecs of wood/garden furniture to find them esp. after its been raining! My nephew loves to worm hunt for us even tho we have worm farms set up. We've also fed them strips of oxliver/oxheart. Ours won't eat axie pellets. Never fed them shrimp, only cos the rest of the household would object, but some axie owners do.
You could remove your axie from tank, while it is cycling and put him in a smaller container (like one of those plastic storage ones) doing complete waterchanges daily on it.