Why do we need a private constructor?

As Stefan, Adam and other have pointed out, private constructors are useful in cases where it is undesirable for a class to be created by code outside of the class. Singletons, factories, static method objects are examples of where being able to restrict constructon of a type is useful to enforce a particular pattern.

To respond to the second part of your question about why singletons are needed if static classes exist: singletons and static classes are not equivalent.

For example, a singleton class can implement an interface, a static class cannot. A singleton object may be passed to methods as a parameter - this is not so easy to do with static classes without resorting to wrapper objects or reflection. There are also cases where you may want to create an inheritance hierarchy in which one (or more) of the leaf classes are singleton - this is not possible with static classes either. As another example, you may have several different singletons and you may want to instantiate one of them at runtime based on environmental or configurational parameters - this is also not possible with static classes.

It is important to understand the language features and choose the right one for the job - they're there for a reason.

Sometimes you shouldn't be able to instantiate a class. This makes this explicit and enforces this at the compiler level.

Singletons are just one use case. Constants classes, static methods classes, and other types of patterns dictate that a class should not be instantiable.

Factory

Private constructors can be useful when using a factory pattern (in other words, a static function that's used to obtain an instance of the class rather than explicit instantiation).

public class MyClass
{ 
    private static Dictionary<object, MyClass> cache = 
        new Dictionary<object, MyClass>();

    private MyClass() { }

    public static MyClass GetInstance(object data)
    {
        MyClass output;

        if(!cache.TryGetValue(data, out output)) 
            cache.Add(data, output = new MyClass());

        return output;           
    }
}

Pseudo-Sealed with Nested Children

Any nested classes that inherit from the outer class can access the private constructor.

For instance, you can use this to create an abstract class that you can inherit from, but no one else (an internal constructor would also work here to restrict inheritance to a single assembly, but the private constructor forces all implementations to be nested classes.)

public abstract class BaseClass
{
    private BaseClass() { }

    public class SubClass1 : BaseClass
    {
        public SubClass1() : base() { }
    }

    public class SubClass2 : BaseClass
    {
        public SubClass2() : base() { }
    }
}

Base Constructor

They can also be used to create "base" constructors that are called from different, more accessible constructors.

public class MyClass
{
    private MyClass(object data1, string data2) { }

    public MyClass(object data1) : this(data1, null) { }

    public MyClass(string data2) : this(null, data2) { }

    public MyClass() : this(null, null) { }
}