If you just got your Solo, it has been in "storage" since it was manufactured. The battery that keeps the Almanac & Ephemeris is long since dead and will require extraordinary measures to get fully recharged again.
The Solo has a large amount of self generated EMI. (Hence the new Solo GPS shield improves performance.) And the long time to fully acquire all the data from a cold start. This is typical of a "new" solo that was manufactured in mid to late 2015.
There are 3rd party M8N receivers that also improve performance by using a "better" GPS module. Those (from Jordi) have the distinct advantage of being manufactured (in the US with the latest rev M8N-0-10) recently and their battery (same as on the original and even Rev 3DR GPS) will be less discharged. The combination makes for a real measurable improvement. YMMV.
Search all the GPS related posts here and you will find a wealth of info.