two auto incrementing columns
If the Queue table is MyISAM, I have just the thing for you.

OPTION #1

First, you should store task names in its own table

CREATE TABLE IF NOT EXISTS `Tasks` (
    `ID` int(11) NOT NULL AUTO_INCREMENT,
    `Task` varchar(255) NOT NULL,
    PRIMARY KEY (`ID`).
    UNIQUE KEY (`Task`)
) ENGINE=MyISAM;


Then, remove Task and TaskID from Queue and change the primary key to (TaskID,ID)

CREATE TABLE IF NOT EXISTS `Queue` (
    `ID` int(11) NOT NULL AUTO_INCREMENT,
    `TaskID` int(11) NOT NULL,
    `Client` varchar(30) NOT NULL,
    `AddedInfo` varchar(255) NOT NULL,
    `Status` varchar(20) NOT NULL,
    `Time` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP,
    PRIMARY KEY (`TaskID`,`ID`)
) ENGINE=MyISAM;


Then, you would do something like this each time

INSERT IGNORE INTO Tasks (Task) VALUES ('Mow the Lawn');
SELECT ID INTO @GivenTaskID FROM Tasks WHERE Task = 'Mow the Lawn';
INSERT INTO Queue (TaskID,Client,AddedInfo,Status)
VALUES (@GivenTaskID,'Rolando Edwards','Valued Customer','Active');
INSERT INTO Queue (TaskID,Client,AddedInfo,Status)
VALUES (@GivenTaskID,'Rolando Edwards','Forgot to Pay','Suspended');
INSERT INTO Queue (TaskID,Client,AddedInfo,Status)
VALUES (@GivenTaskID,'Rolando Edwards','Has Not Paid in 90 Days','Deadbeat');
INSERT IGNORE INTO Tasks (Task) VALUES ('Plant New Flowers');
SELECT ID INTO @GivenTaskID FROM Tasks WHERE Task = 'Plant New Flowers';
INSERT INTO Queue (TaskID,Client,AddedInfo,Status)
VALUES (@GivenTaskID,'Pamela Edwards','First Time Customer','Active');
INSERT INTO Queue (TaskID,Client,AddedInfo,Status)
VALUES (@GivenTaskID,'Pamela Edwards','Made First Payment','Active');


OPTION #2

If you do not want to introduce a new table for tasks then redo the table like this

CREATE TABLE IF NOT EXISTS `Queue` (
    `ID` int(11) NOT NULL AUTO_INCREMENT,
    `Task` varchar(255) NOT NULL,
    `Client` varchar(30) NOT NULL,
    `AddedInfo` varchar(255) NOT NULL,
    `Status` varchar(20) NOT NULL,
    `Time` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP,
    PRIMARY KEY (`Task`,`ID`)
) ENGINE=MyISAM;


Then, you would do something like this each time

INSERT INTO Queue (Task,Client,AddedInfo,Status)
VALUES ('Mow the Lawn','Rolando Edwards','Valued Customer','Active');
INSERT INTO Queue (TaskID,Client,AddedInfo,Status)
VALUES ('Mow the Lawn','Rolando Edwards','Forgot to Pay','Suspended');
INSERT INTO Queue (TaskID,Client,AddedInfo,Status)
VALUES ('Mow the Lawn','Rolando Edwards','Has Not Paid in 90 Days','Deadbeat');
INSERT INTO Queue (TaskID,Client,AddedInfo,Status)
VALUES ('Plant New Flowers','Pamela Edwards','First Time Customer','Active');
INSERT INTO Queue (TaskID,Client,AddedInfo,Status)
VALUES ('Plant New Flowers','Pamela Edwards','Made First Payment','Active');


EPILOGUE

In both cases, you will have ID of 3 for 'Mow the Lawn' and an ID of 2 for 'Plant New Flowers'

I have done this before. See my posts


Apr 21, 2012 : How can you have two auto-incremental columns in one table?
Feb 26, 2013 : How to use 2 auto increment columns in MySQL phpmyadmin


GIVE IT A TRY !!!