Logspace algorithms on graphs with bounded tree width
Tutte polynomial is an example. 

This is a generalization of the chromatic polynomial, which itself is a #P-hard problem in any reasonable formulation. In 


  Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width, S. D. Noble, 
  Combinatorics, Probability and Computing, 1998,


a polynomial time algorithm is given where the time complexity is about $O(f(k)n^{4+\epsilon})$, where $k$ is the treewidth and $n$ is the number of nodes.
Related works can be seen in here. For a survey, there are article on Arxiv, 
where the complexity issue discussed in section 8.

It seems that the problem cannot be expressed in MSO2 directly, though I'm not familiar with the detailed definitions... Hope this problem is what you need!