I hope you are in a niche market (low competition) for this product and found an inexpensive way to get users to your site because given the nature of the product you need a lot of people on the site already in order to get new users to register and/or subscribe.
I am not clear on what "premium" access means on your site - is it access to matches or prospective dates info (something critical to success of the experience) or just some features that offer convenience (a nice to have add-on)? In the freemium model it's important to structure the product in a way that allows users to really try the product and invest time (fill out profile) before they are asked to pay so the free product is hard to give up on.
If you ask to pay for access to "matches" - yes, I would start with giving the product for free (consider a free trial or super low price like 99 cents so you have CC on file) to your first X customers.
If you plan to charge for add-ons that are just convenient to have than you can start charging immediately and can tell early on if people are willing to pay for the premium service and adjust your strategy as needed.
Read this post by Joel on strategy for companies that need to grow big fast:
http://joelonsoftware.com/articles/fog0000000056.html
Extra unsolicited suggestions:
1. To get your "premium feature" right, survey your customers - those that subscribe and those that walk away to see what's heavily used and what's missing.
2. Read this post in pricing strategy by Joel:
http://www.joelonsoftware.com/articles/CamelsandRubberDuckies.html