It currently can't be done without rewriting Magento code.
That attribute on the backend has a specific model it uses
The model is located here: Mage_Catalog_Model_Product_Attribute_Source_Countryofmanufacture
Looking at the logic in the model, it doesn't even call or mention what products are in that specific category. Going further into the Abstract, the Abstract contains no logic for layered navigation.
You can change it to be "filterable (with no results)" but that will only list the all the countries available.
I'm going to tinker with the logic to see if I can get it working, but it wouldnt be a quick fix.
[EDIT]:
Here is a link to a pull request from the Magento bugathon that implemented the required changes in the country of manufacturer and also the boolean source model.
Unfortunately it didn't get merged into the core because the original issue was related to a different source model (the table type).
The fix however will resolve your issues.
https://github.com/magento/bugathon_march_2013/pull/256
Here is the link to a patch containing only source model changes (not the tests):
https://gist.github.com/Vinai/bb1928021811f247c331
Obviously reuse attributes between attribute sets where it makes sense.
The key with attributes is to strike a balance between the number of attributes and attribute options. Its no good having a single colour attribute if you have 3000 options for it. Similarly, its a waste if you have 300 attributes for colour, with only 10 options in each.
The thing with attributes, is whilst desirable to have rich, detailed information for products, it isn't always necessary to break down every possible facet of a product into attributes.
Attributes need only be populated if they are being used, for example if they are used for layered nav., for configurable product creation etc. But if merely just to display product information, there is no reason why you couldn't group the data in a single attribute text field.
Attribute sets usually mirror categories - and there is no good reason to have 2500 categories of products. That being said, attribute sets don't really come with overhead, only the attributes do.
Best Answer
There is no direct connection to the "Custom Options" in a product and an attribute. You would have to simulate this manually. Follow these steps to do that:
Lets say you have a Category called Electronics. And an Attribute Set called Electronics.
Create a new attribute called whatever your Custom Option is, such as Extended Warranty.
When creating the Attribute, under Attribute Properties set Catalog Input Type for Store Owner and select either Dropdown, Multiple Select, or Price. Those are the only ones usable for filterable search.
Then in Frontend Properties select "Use In Layered Navigation".
Then click Manage Label/Options and input the options you would have in the Custom Options of the product.
Add this Attribute to the Electronics Attribute Set.
If you selected Dropdown as Catalog Input Type for Store Owner, then do the same for your Custom Options in the product. So if you had an Electronic, it now has the dropdown attribute for Extended Warranty or whatever attribute you want to use.