Before you give up on boiling, try it longer. I use a giant pot, with a lid from a smaller pot. This way the lid falls in and weighs down the tires so that they stay under water (normally they seem to float). I usually have to boil them until about the 2 hour mark. After that its like peeling good ribs off the bone.