We have the Inline Account Hierarchy app from Salesforce labs installed. It has been installed and working fine since July 2014 and I've made several Change Set deployments since them without incident. I am now suddenly unable to deploy a Flow from our Sandbox to Production, and this application is the one that is failing the code tests. (I don't have a lot of Apex in the system, (I'm not a programmer) and what Apex I do have is all from 3rd party AppExchange apps like this one.) My code coverage has suddenly gone from something like 89% to 29%. on the AccountStructure class 0 out of 133 lines are passing, and other Classes related to this application are getting 41%, 71% and 84% coverage which is all a bit disturbing.

I haven't altered the test scripts since they were installed.
I have turned off the two validation rules that were running against the account object.
I have added a couple of new custom account fields, but they do not have validation statements in them.
I have added one rollup field recently that counts the number of opportunities on the account. 

Since I have no experience in writing test cases, and have never had to deal with code coverage issues before:

Are there other things I should check?
Are there resources I can reference to learn more?
Does anyone have any ideas on how to fix this?

I don't want to have to delete the application because one of our business units relies on it, but it may come to that if I can't deploy things to production!

Specific errors I encounter are:

Class.InlineAcountHerachy_TestUtilities.updateAccountList: line 106, column 1
Class.AccountHierarchyTestData.createTestHierarchy: line 33, column 1
Class.testAccountHierarchy.testAccountHierarchy: line 6, column 1

First error code near error "106, column 1"
101       if ( this.checkObjectCrud('Account', fieldsToCheck, 'create') && !this.testAccList.isEmpty() ){
102         try{
103           update this.testAccList;
104         }
105         catch( Exception ex ){
106          System.assert( false ,'Pre deploy test failed, This may be because of custom validation rules in your Org. You can check ignore apex errors or temporarily deactivate your validation rules for Accounts and try again.');
107        }
108       }
109       else{
110         System.Assert(false , 'You need right over Account Object');
111       }

Second error at line 33, column 1

26         // Create 10 sub accounts
27       testUtils.createAccounts( 10 , fieldsToCheck );
28       Integer i = 0;
29         for ( Account accAux : testUtils.testAccList ){ //Now i need change the names
30           accAux.Name = 'HierarchyTest' + String.valueOf( i );
31             i++;
32         }
33         testUtils.updateAccountList( fieldsToCheck );        
34         
35         List<Account> accountList = [ Select Id, parentID, name from account where name like 'HierarchyTest%' ORDER BY Name limit 10 ];
36                 
37         for ( Integer x = 0; x < accountList.size(); x++ ){
38             if ( accountList[x].name != 'HierarchyTest0' ){
39                 accountList[x].parentID = parentID;
40                 parentID = accountList[x].Id; 
41             }

Last error at line 6, column 1
1 @isTest
2 private class testAccountHierarchy{
3
4     static testMethod void testAccountHierarchy(){
5
6         AccountHierarchyTestData.createTestHierarchy();
7
8         Account topAccount      = [ Select id, name from account where name = 'HierarchyTest0' limit 1 ];
9         Account middleAccount   = [ Select id, parentID, name from account where name = 'HierarchyTest4' limit 1 ];
10         Account bottomAccount   = [ Select id, parentID, name from account where name = 'HierarchyTest9' limit 1 ];
11         Account[] accountList   = [ Select id, parentID, name from account where name like 'HierarchyTest%' ];
12
13         test.startTest();

Any guidance will be greatly appreciated.