Has anyone noticed whether inserting records into a list-type custom setting takes a long time?

I have a managed package that includes 4 custom settings, as well as a trigger that expects the custom settings to be populated with certain records. When the trigger starts, it checks whether the custom settings are populated, and if not, it populates them, inserting about 350 records total, split among the 4 custom settings. It inserts the custom settings using standard Apex techniques for inserting records -- it constructs a List<My_Custom_Setting__c> and then inserts the list with a since insert statement.

One of the custom settings gets populated with about 250 records. Checking the debug logs, I see that it often takes 5 minutes or more for that one insert operation to complete. That, combined with the time it takes to populate the other 3 custom settings, sometimes pushes the trigger over the 10-minute-per-transaction limit. 

I know I can use a Visualforce page to populate the custom settings, and just tell people who install the package to load that page to complete the installation. But I'm more interested in why it takes 5 minutes or more for a single insert statement to create 250 custom setting records. Has anyone else seen that kind of performance issue? Any thoughts on what I could do to avoid it?