We present the corrections to the fermion propagator, to second order in the lattice spacing, O(a^2), in 1-loop perturbation theory. The fermions are described by the clover action and for the gluons we use a 3-parameter family of Symanzik improved actions. Our calculation has been carried out in a general covariant gauge. The results are provided as a polynomial of the clover parameter, and are tabulated for 10 popular sets of the Symanzik coefficients (Plaquette, Tree-level Symanzik, Iwasaki, TILW and DBW2 action). We also study the O(a^2) corrections to matrix elements of fermion bilinear operators that have the form $barPsiGammaPsi$, where $Gamma$ denotes all possible distinct products of Dirac matrices. These correction terms are essential ingredients for improving, to O(a^2), the matrix elements of the fermion operators. Our results are applicable also to the case of twisted mass fermions. A longer write-up of this work, including non-perturbative results, is in preparation together with V. Gimenez, V. Lubicz and D. Palao.