A little googling turns up this blog post from nearer the time, which has a link to the polling firm's website. That link is unfortunately broken, but the Internet Archive is a wonderful thing; here is a link to that page as it was in early 2007.
The specific question was apparently "Would you support or oppose there being areas of Britain which are pre-dominantly Muslim and in which Sharia Law is introduced?". 40% said support, 41% said oppose, 19% don't know.
So, if the poll was conducted well then up to its margin of statistical error the answer is yes (although there's a subtle difference in the question being asked; some respondents might have interpreted this as asking, e.g., about creating new communities for Muslims who want sharia law applied to them; and as Glen O notes in comments, only "support" and "oppose" answers were offered and maybe some people who didn't exactly want sharia law introduced anywhere might have picked "support" if they thought "oppose" was too strong).
The polling organization was ICM, which is a reputable firm. They say this:
ICM interviewed a random sample of 500 Muslim people by telephone between 14-16th February 2006. Muslim people were initially identified from a much larger sample of all adults interviewed on large scale random telephone surveys conducted by ICM. Those who said they are Muslim were re-interviewed for this survey. In order to achieve the sample of 500, some respondents were asked for the telephone numbers of another Muslim. In all 43 interviews were achieved in this way. The data has been weighted to the profile of British Muslims according to the 2001 Census. ICM is a member of the British Polling Council and abides by its rules.
500 is not a very large number; one standard deviation of error in this sample would be about 2%, suggesting that in so far as they picked a good sample we should be reasonably confident that the population-wide figure was between about 35% and about 45%. The sampling methodology doesn't sound great to me ("some respondents were asked for the telephone numbers of another Muslim" -- surely this is going to introduce correlations and biases) so I'd be unsurprised if the error were a bit larger.
It's also worth paying some attention to the context. The poll was conducted a week after the Muslim cleric Abu Hamza was sentenced to several years in prison for incitement to hatred and murder, and at a time when tensions were running high about the Jyllands-Posten cartoons of Muhammad. That may have had some impact on responses in the poll.
Another remark from Glen O in comments: "Sharia law" isn't just about cutting off thieves' hands and killing apostates and so forth, but also applies to religious obligations like praying five times a day, and civil matters like inheritance. It's hard to know what aspects of sharia respondents in this survey were thinking of when they answered as they did; it will not necessarily be the more inflammatory ones that might jump to the minds of non-Muslim readers.
In conclusion, I think
- The answer is basically yes.
- There really was such a poll. It was conducted by a reputable pollster for a major newspaper. The question asked was near enough to the claim in the question, but the differences are worth being aware of.
- The sample size wasn't very large and the sampling methodology wasn't great, so the figure might not be very accurate.
- Tensions between Muslims and others in the UK were unusually high when the poll was taken; Muslims' expressed opinions at that time may be less than perfectly informative about their opinions in more normal times.