Formula field is not Working as expected

Assuming your formula was copied directly from salesforce.com, the problem has to do with "Smart Quotes." Salesforce formulas don't recognize “ and ” as actual quotation marks. Try using the following:

IF(
BEGINS(WhatId, "006"), "Opportunity",

IF(
BEGINS(WhatId, "001"), "Account",

IF(
BEGINS(WhoId, "00Q"), "Lead",

IF(
BEGINS(WhoId, "003"), "Contact",""))))

Coincidentally, you could shorten your formula:

CASE(LEFT(WhatId, 3), "006", "Opportunity", "001", "Account",
CASE(LEFT(WhoId, 3), "00Q", "Lead", "003", "Contact", ""))

Honestly, I think you're better off writing a before trigger. The obvious advantage of the below strategy is that it scales to all objects you can use for these polymorphic lookups. I did check that you can't use What.Type or Who.Type in a formula.

For the Apex approach, you just need to call (using the handler pattern of your choice):

public static void updateWhatType(List<Task> records)
{
    for (Task record : records) record.WhatType__c = getType(record.WhatId);
}
public static void updateWhoType(List<Task> records)
{
    for (Task record : records) record.WhoType__c = getType(record.WhoId);
}
public static String getType(Id value)
{
    return (value == null) ? null : String.valueOf(record.WhatId.getSObjectType());
}