The only time we've heard of that issue is if the permissions for the Page are wonky. I can see the Page on Facebook just fine, so I'm not sure if this is the cause. Either way though, can you click the Edit Page button from your Facebook Page and check the "Manage Permissions" area.
If your page is limited to certain countries or age ranges the plugin won't be visible except to users who meet those restrictions.
Hope that helps get you started, but if not, let us know.
Thanks,
Alex