Summary: In general, EU citizens can enter any other EU country and travel or work freely but not necessarily stay as long they want, especially if they don't have a job. Full freedom of movement means that Romanian and Bulgarian citizens now have the same rights as other EU citizens, without the job market restrictions that applied to them until 2014.
The free movement of persons is, together with the free movement of goods, services and capital, one of the cornerstones of the single market. It's been in the treaties since the beginning (the 1959 treaty of Rome establishing the European Economic Community).
There is an extensive body of secondary legislation and case law about it but it is all rooted in what is now article 45 of the TFEU:
- Freedom of movement for workers shall be secured within the Union.
The details are complex but as you can plainly read, it only applies to workers.
On top of this fundamental principle, the 1992 Maastricht treaty created the notion of an EU citizenship and added a right to move and reside freely for economically non-active people, as laid out in article 21 (1) of the TFEU:
- Every citizen of the Union shall have the right to move and reside freely within the territory of the Member States, subject to the limitations and conditions laid down in the Treaties and by the measures adopted to give them effect.
Here again, the details are complex, there is a lot of secondary legislation and the court has interpreted this right pretty liberally but you can already notice that the language is more guarded.
Consequently, the right to reside for economically non-active persons is more restrictive than the freedom of movement for workers. Specifically, the most important “limitations and conditions” are laid out in article 7 of Directive 2004/38/EC (emphasis mine)
- All Union citizens shall have the right of residence on the territory of another Member State for a period of longer than three months if they:
(a) are workers or self-employed persons in the host Member State; or
(b) have sufficient resources for themselves and their family members not to become a burden on the social assistance system of the host Member State during their period of residence and have comprehensive sickness insurance cover in the host Member State; or
(c) – are enrolled at a private or public establishment, accredited or financed by the host Member State on the basis of its legislation or administrative practice, for the principal purpose of following a course of study […]
(d) are family members accompanying or joining a Union citizen who satisfies the conditions referred to in points (a), (b) or (c).
So there is no absolute right to reside in other EU countries but four different ways to gain this right. Point (a) is for workers, point (c) is for students and point (d) is for family members accompanying another EU citizen who qualifies under (a), (b) or (c) (it's a derived right).
If you don't qualify for either of those, you're left with point (b) and it comes with a big caveat: you should not “become a burden on the social assistance system”. In practice, it means you must have resources above the level to qualify for welfare benefits in the host country. That's the legal basis for France's treatment of Romas, for the requirements to get residence cards in Spain or Portugal, for Belgium expelling EU citizens, etc.
France therefore cannot apply restrictions to Bulgarian and Romanian citizens per se and cannot require them to apply for a permit to work in France anymore. But it can still ask EU citizens (from all member states) to leave under certain conditions. Also note that when it happens, EU citizens are not detained or forcibly removed like non-EU citizens regularly are; they are asked to leave and sometimes given a bit of cash to pay for their trip (there have also been media reports of “camps” being “evacuated” or destroyed by the police but that's an internal police matter based on building regulations, zoning, laws against trespassing and loitering, etc. but not directly on residency requirements).
By contrast, the rights to visit for less than three months or to reside as a worker or a family member are more extensive. They can only be restricted (e.g. by denying entry or actually detaining and deporting someone) on grounds of “public policy, public security or public health”. It might sound a bit vague but that's a very stringent test, narrowly interpreted by the court. It could for example be the case of someone found guilty of a serious crime and under a deportation order.
Consequently, the people who were asked to leave France or Belgium because they do not qualify for the “right of residence” can typically come back more-or-less immediately. They can be denied the right to stay in the country long-term without a job or financial resources but not banned entirely or prevented from travelling or working freely. Any such ban would also be very difficult to enforce given France's situation in the Schengen area (for third-country nationals, wanted criminals, etc. it's possible to communicate a ban or request to arrest a person to all Schengen countries using somethign called the SIS but it's not possible to use that for EU citizens who committed no crime).
That's what “freedom of movement” means in the EU but the sentence you quoted also adds a small nuance. After the last three waves of enlargement of the union (the 2004 and 2007 Eastern enlargements and Croatia in 2013), older member states reserved the right to apply additional transitory restrictions and in particular to restrict access to their job market for citizens of the new member states. Some countries like the UK decided not to do it but many did. As of writing, such restrictions still apply to Croatia but the last ones for Romania and Bulgaria expired at the beginning of 2014 (7 years after these two countries became EU members).
So “full freedom of movement” does not mean absolute or without limitation but it means that Bulgarian and Romanian citizens are now finally able to enjoy this freedom of movement to the same extent than citizens from other EU nations, everywhere in the EU (but not in Switzerland yet as the bilateral agreements between the EU and Switzerland add another layer of complexity to all this).
Incidentally, none of this has anything to do with Schengen at all (but that didn't stop the French government from making noise about Romania's entry into the Schengen area just to show it was “doing something” about immigration from Romania, which is absurd because it does practically nothing to stop Romanian citizens from coming to France).
When a Romanian citizen shows up at a Schengen external border, he or she only needs to show his ID and would be let through without any question or further control, except perhaps a database check (article 7(2) of the Schengen Borders Code). Their ID should be checked but that's to establish that they are in fact who they say they are and therefore covered by the EU freedom of movement. Beyond that, border guards have very little discretion in this case.