I find Maxis coverage is going from bad to worst day by day.
Last time it used to be pretty good andden soon, my phone always no line or half bars only. I thought it was my sim card problem at first as that was what they tell me. So I went to get my sim card changed. Now it's still like this. And lots of places no 3G also.

Is your sim card quite old? They say sim card lifespan around few years only. If like 4-5 years then maybe a bit faulty edi.