Do you know how the carbohydrate is attached to the protein? Is it N-, or O-linked (linked to an Asn, or a Ser/Thr)? PNGase F will only remove carbohydrates attached to an Asn. O-Glycosidase will remove core 1 and core 3 O-linked disaccharides attached to Ser/Thr. If you are certain you have O-linked carbohydrates, make sure that you have treat your glycoprotein with Neuraminidase, and denature the protein prior to deglycosylation. The secondary and tertiary structure of proteins can prevent endoglycosidases from reaching their substrate, thus making denaturation a crucial step in efficient cleavage. If you do not want to denature then consider adding more enzyme and longer incubation times. If you have denatured the protein, be certain to add NP-40 (to protect O-Glycosidase from the SDS in the denaturation step).