<p>A number of business areas I work with use a folder structure to organise their Sharepoint housed documents (not ideal I know, but we're stuck with it).  </p>

<p>I would like to use a web part page to present a number of views of their document libraries based on the subfolders that the documents appear in, but this is proving more difficult than I had thought.  Has anyone overcome this problem in the past?</p>

What kind of document library information do you want in the view?
How do you want the user to filter the view?
In general the most powerful way of creating views in sharepoint is with the data view web part.
http://office.microsoft.com/en-us/sharepointdesigner/HA100948041033.aspx
You will need Microsoft Office SharePoint Designer.
You can present different views of you folders using the data view filter and sorting controls.
You can use web part connections to filter a dataview.
You can use any datasource linked to say a drop down to filter a dataview.
How to tie a dropdown list to a gridview in Sharepoint 2007?