This is an excellent question.
The category of fixed income investments generally includes all kinds of bonds and preferred shares and other instruments that pay a fixed rate of return and are expected to return your principal by some maturity date. The spectrum of fixed-income investing is wide.
For the fixed income component of a personal investment portfolio, I'd look to investing in high quality, short-term government bonds or index funds and ETFs composed of such. Consider also holding some to protect against inflation – such as Treasury inflation-protected securities (TIPS) in the U.S., or Real Return Bonds (RRBs) in Canada.
Corporate bonds, junk bonds, long term bonds, strip bonds, convertible bonds or debentures, and preferred shares ought to be avoided by investors who do not understand well the make-up and risks of such investments.
Also, structured products like CDOs (collateralized debt obligations), ABCP (asset-backed commercial paper), MBS (mortgage-backed securities), etc. should be avoided. While originally marketed as high-quality fixed income investments, many structured products blew up during the credit crisis and left investors with a capital loss on their supposed "safe" investment.
On the subject of CDs / certificates of deposit (or GICs / guaranteed investment certificates in Canada): Yes, they can be considered fixed income investments, in that they yield a fixed rate of return and are expected to return one's principal at maturity.
However, if a fixed income investment's maturity is short (e.g. less than one year), and the quality high (e.g. government paper or insured deposits), and it can be liquidated before maturity if desired (at slight penalty), then such a fixed income investment could instead be considered part of the cash or cash equivalents component in a portfolio, since there is little risk of significant loss of principal due to interest rate fluctuations, and the money is accessible if necessary. Whereas, if a CD can't be sold before maturity, I would personally consider it fixed income yet not a cash equivalent until maturity.