In this paper, we present an a-posteriori probability (APP) decoding algorithm for non-binary block codes on non-binary Gilbert-Elliott channels (GECs) using generalized weight polynomials. The proposed approach is based on a single-sweep APP decoding technique that utilizes matrix multiplications. By fixing the crossover probability in the `bad' state of the non-binary GEC such that for a given transmitted symbol, all symbols are equally likely to be received, an APP decoding decision can efficiently be reached by evaluating trivariate polynomials. In this case, the non-binary GEC is described by three variables that are referred to as the average fade to connection time ratio, the burst factor, and the channel reliability factor. The application of the generalized weight polynomial approach is demonstrated with respect to numerical performance results obtained for simple non-binary block codes from computer simulations.