What I found out later is, the SetItemDataSources method searches the report's data sources for the name you have set, i.e this name is not the shared data sources' name, but the data sources that is in the rdl file (in the <DataSources> tag).
So in order to fix that, we need to tell the reporting service that the report's data source with the name X (which we will see how to find it out) is still there, but it will reference to the shared data source.
so now lets get our hands dirty with some code.
How to
//Get the Shared Data Source
DataSource[] ds = GetSharedDataSource(service, reportsFolder, reportName);
// Set Report's DataSource
service.SetItemDataSources(@"/" + reportsFolder + @"/" + reportName, ds);
public static DataSource[] GetSharedDataSource(ReportingService2005 service, string reportsFolder, string reportName)
{
DataSourceReference reference = new DataSourceReference();
DataSource ds = new DataSource();
reference.Reference = "/" + reportsFolder + "/" + "SharedDataSource";
ds.Item = (DataSourceDefinitionOrReference)reference;
// Get original report Data Source Name
DataSource[] reportDataSource = service.GetItemDataSources(@"/" + reportsFolder + @"/" + reportName);
ds.Name = reportDataSource[0].Name;
return new DataSource[] { ds };
}