Where are you presently? Do you want to stay for a long time in Greece or move quickly to another EU member state?
Do Bulgarians face any restrictions on working in Greece presently?
I suspect you will find it easier on the ground than what he is presently reporting. When you plonk down your two passports and marriage certificate, that tends (usually) to focus people on the fact that you are European.
This EU service may be helpful for getting more information now:
http://ec.europa.eu/citizensrights/
And if you have problems once on the ground, you should contact Solvit:
http://eumovement.wordpress.com/help-eu-solvit/