Ajax Request Times Out (or Is Really Slow)

My basic structure is that I have a table on a page, which I want to reload without refreshing the entire page. So on clicking a button on the page it fires of this:

function RefreshMissionsAjax() {
//fade out the old table.
$(clientID('MissionsDisplay')).fadeOut(500);
//request the new value from the page (calls the GetIncompleteMissions() method in the MissionViewer.aspx.cs page)
$.ajax({
type: "POST",
url: "MissionViewer.aspx/GetIncompleteMissions",
data: "{}",
contentType: "application/json; charset=utf-8",
dataType: "json",
success: function (msg) {
$(clientID('MissionsDisplay')).html(msg.d);
$(clientID('MissionsDisplay')).fadeIn(500);
},
error: function (xhr, ajaxOptions, thrownError) {
$(clientID('MissionsDisplay')).html('An error occured while trying to refresh the page data.');
$(clientID('MissionsDisplay')).fadeIn(500);
}
});
}
And I have in the code bedind of an aspx page:
[WebMethod]
public static string GetIncompleteMissions()
{
return GetHTMLTable();
}

This method just grabs some data, and creates a html table - nothing too fancy. When the returned table is small (a dozen rows or less) then it works like a charm. But when it gets larger, it takes a long long time. At 100 rows it can take 5 minutes to render the table. At 1000 rows I have left it for 30 minutes and nothing will happen after the fadeout. (NB - it loads fairly quickly on the pageload, before the ajax refresh is used, so it is not the actual server side creation of the table thats the problem).

This is my first real attempt at doing something like this, so I dont know if this is the best way to do it - it was just something i pieced together that worked great when i was testing with small datasets. Now, not so much.