Dimension Reduction in Categorical Data with missing values

Regarding imputation of categorical data, I would suggest to check the mice package. Also take a look at this presentation which explains how it imputes multivariate categorical data. Another package for Mutliple Imputation of Incomplete Multivariate Data is Amelia. Amelia includes some limited capacity to deal with ordinal and nominal variables.

As for dimensionality reduction for categorical data (i.e. a way to arrange variables into homogeneous clusters), I would suggest the method of Multiple Correspondence Analysis which will give you the latent variables that maximize the homogeneity of the clusters. Similarly to what is done in Principal Component Analysis (PCA) and Factor Analysis, the MCA solution can also be rotated to increase the components simplicity. The idea behind a rotation is to find subsets of variables which coincide more clearly with the rotated components. This implies that maximizing components simplicity can help in factor interpretation and in variables clustering. In R MCA methods are included in packages ade4, MASS, FactoMineR and ca (at least). As for FactoMineR, you can use it through a graphical interface if you add it as an extra menu to the ones already proposed by the Rcmdr package, installing the RcmdrPlugin.FactoMineR