The UK has adopted a definition of spouse in the that excludes parties to a marriage of convenience, in section 2(1) of the Immigration (European Economic Area) Regulations 2006:
“spouse” does not include a party to a marriage of convenience;
This is in contrast to the freedom of movement directive itself (2004/38/EC), which does not define spouse. However, it is certainly arguable that the definition is allowed under Article 35 of the directive, which reads
Abuse of rights
Member States may adopt the necessary measures to refuse, terminate or withdraw any right conferred by this Directive in the case of abuse of rights or fraud, such as marriages of convenience. Any such measure shall be proportionate and subject to the procedural safeguards provided for in Articles 30 and 31.
So, unless you want to go to court to challenge the UK's definition of spouse (a challenge which seems unlikely to succeed), you must accept that it excludes parties to a marriage of convenience.
The exclusion of marriages of convenience implies an ability to investigate marriages to determine whether they are in fact marriages of convenience. In that light, the UK's own guidance on the issuing of EEA family permits says
EUN2.10 What if I suspect a marriage / civil partnership of convenience?
The definition of ‘spouse’ and ‘civil partner’ in the EEA Regulations does not include someone who has entered into a marriage / civil partnership of convenience.
When a marriage / civil partnership of convenience is suspected, the burden of proof is high and rests with the ECO. However, in these cases the ECO is entitled to interview the applicant. Factors to consider include:
- an adverse immigration history;
- doubts about the validity of documentation;
- application follows soon after the marriage / civil partnership;
- no previous evidence of the relationship.
The ECO should not consider the following cases as marriages / civil partnerships of convenience where:
- there is a child of the relationship;
- there is evidence to suggest cohabitation.
So your marriage fits one of the grounds for suspicion (application soon after marriage), and doesn't fit either of the grounds for non-consideration (you have no child and, I assume, you have not lived together).
(If you have lived together, then you should submit evidence of that fact, which should suffice to overcome the officer's suspicions about the validity of your marriage.)
As I have alluded to in a comment, there are many stories floating around the web of people whose applications were refused improperly on the grounds of marriage of convenience. If the entry clearance officer (ECO) suspects a marriage of convenience, he or she is supposed to develop actual evidence to support that suspicion, and it sounds like that may not have been done here.
The refusal formula suggested in the guidance says "I am satisfied that you are party to a marriage of convenience," which reflects the ECO's burden of proof to establish that a marriage of convenience exists. If the ECO did not use this formula, instead saying "I am not satisfied that your marriage is genuine" or the like, you may have grounds for appeal. Also, if the ECO used that formula but did not actually develop any evidence aside from the timing of your marriage, you may have grounds for appeal.
However, appeal requires payment of a fee, and may be time consuming. It might be faster just to resubmit a new application, as advised in Crazydre's answer, which is free of charge, including the evidence of your relationship.
There is a third possibility: if the ECO clearly did not follow the guidance, you can get in touch with the Entry Clearance Manager (ECM) at the consulate or embassy and complain. This has apparently been successful in some cases.
You might therefore try a two-pronged approach: First, write to the ECM and, if that is unsuccessful, file an appeal; second, file a new application.
I am reluctant to offer specific advice in your case, however, as we have not seen your refusal notice, so we do not know exactly what the ECO said in refusing the application.