Usage of Mutex in c#

The problem here is that all your callers are using a different mutex; you need the locking object to be shared, usually by making it a field. For example, and switching to a simpler lock metaphor:

private readonly object syncLock = new object();
public void ThreadSafeMethod() {
    lock(syncLock) {
        /* critical code */
    }
}

or using the mutex:

private readonly Mutex m = new Mutex();
public void ThreadSafeMethod() {
    m.WaitOne();
    try {
        /* critical code */
    } finally {
        m.ReleaseMutex();
    }
}

This pattern does no locking at all. Every thread creates a new Mutex object and immediately owns the lock for it. Other threads create and use a new Mutex itself.

Consider using a regular lock()!

lock(_lockobject) {
   // do inside what needs to be done - executed on a single thread only
} 

where _lockobject is a simple private variable in your class:

private object _lockobject; 

Edit: thanks to the commenters! Situations exist, where lock(this) can be dangerous. So I removed that.

It looks like you give each Thread its own Mutex. That won't work.

And a Mutex is overkill in most situations. You only need:

private static object syncLock = new object();  // just 1 instance

....

lock(syncLock)
{
    // critical section
}