Tosfos (Menachos 66) writes that since sfiras ha'omer is derabbanan one is permitted to count during bein hashemashos based on the principle of sfeika derabbanan l'kula (interesting to note that Tosfos clearly holds that sfeika derabbanan l'kula does not just mean that ex post facto one may be lenient when faced with the potential uncertain violation of a Rabbinic prohibition, but one may even create such a situation of uncertainty and take advanatge of it). According to the view of the Rambam that sfira is a din d'oraysa, counting during bein hashemashos would involve the uncertain fulfillment of a mitzvah and therefore not be acceptable.
On a practical level, while we pasken like Tosfos, there is still another factor that needs to be accounted for. When exactly is bein hashemashos? According to the GR"A (explaining the view of the Geonim), bein hashemashos begins immediatly after what we refer to as sunset. However, Rabeinu Tam holds that there are two twilight bein hashemashos periods. The bein hashemashos of the GR"A which begins at sunset according to Rabeinu Tam is still considered day. It is not until 50 minutes later that a second bein hashemashos period begins that ia called twilight and it is that 12 minute period which is a safeik day/night.
(I am using the 72 minute standard for simplicity's sake, but the actual time between sunset and nightfall both according to GR"A and R"T may be a variable measure depending on one's location and the time of year.)
If one wishes to count immediatly after what we call sunset, one is faced with a sfeik sfeika l'chumra as follows: 1) safeik whether the follows the Rambam and one can never count during twilight; 2) even if the halacha is like Tosfos, safeik whether Rabeinu Tam is right and bein hashemashos does not start until much later.
Usually the principle of sfeik sfeika is used as a leniency -- here it results in a stringency!
Had you asked me I would have said that counting right after sunset should therefore be prohibited, but there are smarter people than myself who know that R' Akiva Eiger clearly writes that one can be lenient on a Rabbinic prohibition even where there is a sfeik sfeika l'chumra. The Shulchan Aruch (O.C. 248) writes that travelling on a boat on Shabbos outside the techum would be prohibited, but if there is even the possibility that the boat sits higher than 10 tefachim off the sea bottom one can be lenient. R' Akiva Eiger points out the the issue of whether the prohibition of techumin applies 10 tefachim off the ground is an unresolved safeik. Therefore, the S.A.'s case should be a sfeik sfeika l'chumra: 1) a safeik whether the boat is within 10 tefachim of the sea bottom and therefore there is a definite techum violation; 2) even if the boat is above 10 tefachim there remains a safeik whether the issur of techumin applies above 10 tefachim or not. Yet, we see in this case that the Shulchan Aruch paskens that we may be lenient. The same applies to our case of sefiras ha'omer (see Yechaveh Da'as I:23).
Now we have a source, but the question remains why this should be so. Sfeik sfeika is usually understood as a type of rov -- I start with a 50-50 safeik and then add an additional doubt that further tips the balance. You flip a coin once and the odds of heads vs. tails are 50-50; flip the coin twice and the odds of getting heads twice in a row is cut down to only 25%. In our case the rov works l'chumra -- the odds are 75% in favor of waiting until real nightfall and there exists only a 25% chance that the two leniences of Tos. and the GR"A are both right and counting early is permitted. I don't know of any source that says that we disregard rov when it comes to a question of whether a Rabbinic prohibition is being violated -- so why is this scenario different? Something to think about (seems to me there is more than one good answer...)