Strange as I would have thought the other way would have worked. 

Here is the working code with full coverage - hopefully someone may find it useful 

Trigger

trigger OpportunityTrigger on Opportunity (before insert, before update) {
	
	/**
	*	@author			Mike Gill
	*	@date			28/07/11
	*	@description	Main Opportunity Trigger
	*/
	
	// Call Opportunity Controller
	OpportunityTriggerHandler handler = new OpportunityTriggerHandler();  
	
	if(Trigger.isInsert && Trigger.isBefore){
		handler.OnBeforeInsert(Trigger.new);

	}
	
	else if (Trigger.isUpdate && Trigger.isBefore){
		handler.OnBeforeUpdate(Trigger.old, Trigger.new, Trigger.newMap); 
	
	}

 	

}

 Class

public with sharing class OpportunityTriggerHandler {
	
		/**
		*	@author			Mike Gill
		*	@date			28/07/11
		*	@description	Update account type based on certain criteria
		*/

     
     public OpportunityTriggerHandler(){}
	
	//TODO: Add user custom persmission check
	
	 public void OnBeforeInsert(Opportunity[] newOpps){
	 	
		List<Account> accs = new List<Account>();
		
		 // Create empty set
     	Set<Id> accountIds = new Set<Id>();
		
		// Populate set with updated account ids     	
		for (Opportunity opp:newOpps){
				accountIds.add(opp.AccountId);
		}
		
		// Iterate accounts where type is Lead Acct or Stalled Acct
		for (Account acc: [select Id, Type from Account where (Type = 'Lead Acct' or Type = 'Stalled Acct') and Id IN: accountIds]){
			acc.Type = 'Opportunity Acct';
			accs.add(acc);
			
		}
		
		// Update accounts
		update accs;
	     
     }
     
     public void OnBeforeUpdate(Opportunity[] oldOpps, Opportunity[] updatedOpps, Map<Id, Opportunity> oppMap){
     	
     	// Create list for bulk update of accounts
     	List<Account> accs = new List<Account>();
     	
     	// Create empty set of accounts to be updated
     	Set<Id> accountIds = new Set<Id>();
     	
     	// Iterate updated Opps for related accountids
		for (Opportunity opp:updatedOpps){
			// Add acocunt ids where opportunity is lost
			if (opp.StageName == '8-Closed Lost'){
				accountIds.add(opp.AccountId);
			}
		}
     	
     	
     	for (Account acc:[select Id, Type, Opportunity_Counter__c from Account where (Type = 'Lead Acct' or Type = 'Opportunity Acct') and Opportunity_Counter__c = 1 and Id IN: accountIds ]){
     
     		accs.add( new Account (id=acc.id, Type = 'Stalled Acct' ));
  
     	}
     	
     	update accs;

     	
     }

}

Test Class

@isTest
private class TestOpportunityTriggerHandler {
	
	/**
	*	@author			Mike Gill
	*	@date			28/07/11
	*	@description	Test Scenarios for Opportunity Trigger Handler
	*  	TODO: 			
	*/
	
	static List<Account> accounts;
	
	static List<Opportunity> opps;
	static List<Contact> contacts;
	
	
	
	static { 
			
			// Empty Lists	
			accounts = new List<Account>();
    		opps = new List<Opportunity>();
    		contacts = new List<Contact>();
		
			// Fetch profile id
     		Profile p = [select id from Profile where name = 'Standard User'];
     		
     		// Create user for tetsing
     		User u = new User ( alias = 'testme', email = 'testme@noemail.com', emailencodingkey = 'UTF-8', lastname = 'test',languagelocalekey = 'en_US', 
     		localesidkey = 'en_US', profileid = p.Id, country = 'United Kingdom', timezonesidkey = 'Europe/London', username = 'testme@noemail.com');
     		insert u;
     		
     		// Add  Accounts to the list to be inserted	
     		for (Integer i = 0; i<1; i++){
     			Account a = new Account(
     			Name = 'Test Accts' + i,
     			Type = 'Lead Acct',
     			BillingState = 'CA',
     			Industry = 'Business Services',
     			OwnerId = u.Id
     			);
     			accounts.add(a);
     		}
     		
     			insert accounts;
     	
     		
     		// Add Contacts to the list to be inserted
     		for (Account a: accounts){
     			
     			Contact c = new Contact();
     			c.FirstName = 'Test Contact First';
     			c.LastName = 'Test Contact Last';
     			c.LeadSource = 'Call In';
     			c.AccountId = a.Id;
     			contacts.add(c);
     			
     		}
     		
     		insert contacts;
     		
     
     		
    		
    		for (Account a: accounts){
     			
     			Opportunity o = new Opportunity();
     			o.Name = 'Test Opp';
     			o.AccountId = a.Id;
     			o.CloseDate = Date.today();
     			o.StageName = '1-Qualified Prospect';
     			
     			
     			
     			opps.add(o);
     			
     		}
     	
     
  	
		
	}
	
	
    static testMethod void myUnitTest_CreateOpp() {
    	
    /**
    * @description	Test related account type is set to Opportunity Acct on create of opportunity
    */

			// Start test
			test.startTest();

     		insert opps;
    		
    		// End test
    		test.stopTest();
       		
    }
    
    static testMethod void myUnitTest_UpdateOpportunity(){
    	
    	insert opps;
    	
    	List<Opportunity> oppsToUpdate = new List<Opportunity>();
    	
    	for (Opportunity opp:opps){
    		
    		opp.StageName = '8-Closed Lost';
    		oppsToUpdate.add(opp);
    	}
    	
    	test.startTest();
    	
    	update opps;
    	
    	test.stopTest();
    	
    }
  
}