New PayG sim card in Curve 9360: sim card invalid

blackberry curve 9360 PRD_40657_015 MODEL REM71UW

Does the SIM have a BIS account attached to it? Older BlackBerrys like that won't work without BIS.

sounds more like a locked to a carrier story. You need to get it unlocked first.