It's important to note that in order to get the items in the subfolders of a given List, you must specify the Folder in QueryOptions (when invoking the GetListItems operation, that is). Otherwise, it seems you just get the top level items in the given List.
I've discovered a couple of other useful tips.
One is to use the query parameter to narrow down results returned by GetListItems. For example, I have a few cases where I only have the GUID for a particular file or folder but not the URL. So far, I haven't found another way to do this except to search the List items. Fortunately (if I at least know the List) a query makes this pretty simple. The SOAP request looks, in part, like this:
<soap:query>
<Query>
<Where>
<Eq>
<FieldRef Name="UniqueId"/>
<Value Type="Lookup">
{552bef05-b62c-4c76-a217-35e85a1507f1}
</Value></Eq>
</Where>
<OrderBy>
<FieldRef Name="Modified"/>
</OrderBy>
</Query>
</soap:query>
Another useful operation is GetObjectIdFromUrl from the Webs service. Given a URL, this will return some helpful properties for the URL such as the List it belongs to, its ListItemId, and whether it represents a file or a folder.