What sim are you using? Most of the newer SIMs are 32k (or 64k), the older ones being 8k or 16k, which is sometimes a problem on older handsets (i.e. not accepting 32k+ sims). Some phones get around this with firmware updates - not sure how it works with the BMW handset.
Perhaps if you can find an older SIM card to test, it might help narrow down the issue. With some operators, 16k or 32k is stamped on them, but not always. If someone has not upgraded for a few years, chances are they might have a 16k sim which you can test with.
Also don't know if the local operators still supply you with the older sim on special request (MTN used to at some point). They used to do when the first introduced 32k and some people had problems in their handset. However, now that these old handsets are disappearing from the market, they only supply the newer sims.