It sounds to me that some indexes or table keys were not restored or not restored properly. The initial long execution time would seem to indicate that table scans are happening instead of indexed lookups. After the initial query the tables are cached for a while which gives you improved response time.
