The Design patterns book gives the following applicability for the Flyweight design pattern (bold emphasis mine):

Applicabilty

The Flyweight pattern’s effectiveness depends heavily on how and where it’s used. Apply the Flyweight pattern when all of the following are true:

• An application uses a large number of objects.
• Storage costs are high because of the sheer quantity of objects.
• Most object state can be made extrinsic.
• Many groups of objects may be replaced by relatively few shared objects once extrinsic state is removed.
• The application doesn’t depend on object identity. Since flyweight objects may be shared, identity tests will return true for conceptually distinct objects.

Instead of storage costs (space resources), would instantiation costs (time resources) make for a valid application as well?

The Flyweight design pattern is just a special application of caching. In a scenario where you cannot cache an entire object, because some of the object's state is unique, Flyweight reminds us that we may still cache part of the object, if we separate a part that is not unique and can be shared.

Since Flyweight is nothing more than partial caching, it provides generally the same benefits as caching, including reduction in time & space complexity. Therefore, the answer to your question is yes, instantiation costs (time resources) make for a valid application of the Flyweight pattern. Of course this is assuming you can't just cache entire objects, which is altogether simpler than caching parts of them.