Faits: A. Par décision du 20 mai 1999, l'Office de l'assurance-invalidité pour les assurés résidant à l'étranger (ci-après : OAI) a refusé d'allouer une rente d'invalidité à D._, ressortissant belge domicilié en France, au motif que les dispositions conventionnelles entre la Suisse et la Belgique ne permettaient pas le paiement d'une rente d'invalidité à un ressortissant belge domicilié dans un Etat tiers. Cette décision n'a pas été attaquée. Le 31 octobre 2002, l'OAI a alloué au prénommé une rente entière d'invalidité à partir du 1er juin 2002, date de l'entrée en vigueur de l'Accord du 21 juin 1999 entre la Confédération suisse, d'une part, et la Communauté européenne et ses Etats membres, d'autre part, sur la libre circulation des personnes (Accord sur la libre circulation des personnes [ALCP]). Le début de l'invalidité (et du droit théorique à la rente) a été fixé au 6 décembre 1997. B. Par jugement du 15 mai 2003, la Commission fédérale de recours en matière d'assurance-vieillesse, survivants et invalidité pour les personnes résidant à l'étranger a rejeté le recours formé par D._ contre cette décision. C. Ce dernier interjette recours de droit administratif contre ce jugement dont il requiert l'annulation, en concluant au versement de la rente précitée avec effet rétroactif au 6 décembre 1997. L'OAI conclut au rejet du recours, tandis que l'Office fédéral des assurances sociales a renoncé à se déterminer. 