If you have a data plan and service, GSM based Blackberries will download almanac/ephemeris data to reduce the cold start time. With out that, it has to wait to get the data from the sat. Like all GPS devices, with a cold start the better view you have of the sky, the shorter the time to first fix is, especially with a cold start.
Dubdub's advice is still good, if you can't get a lock, take it outside to a place with a good view of the sky. Have a latte, or a smoke and give the chip time to do the work.
My other Blackberry is a PlayBook.