[Windows Mobile Software Development] l3v5y:
Got it!

These are the bits that look relevant, the whole log file is attached as well.

Message: Loading \UpdateBin\Packages\CommonNonEA.cab.pkg as CAB file
Attempting to add Package named \UpdateBin\Packages\CommonNonEA.cab.pkg to Graph.
BuildFileList for node
Attempting to retrieve file info for 7bb5f499-6b7f-4ee0-bcb9-a89ae3fc3e2c.dsm
Attempting to retrieve file info for 7bb5f499-6b7f-4ee0-bcb9-a89ae3fc3e2c.rgu
Added file info for 7bb5f499-6b7f-4ee0-bcb9-a89ae3fc3e2c.rgu to file list
Done building file list for
Major: 5 Minor: 2 QFELevel: 5082 BuildNumber: 21870
Target: Major: 0 Minor: 0 QFELevel: 0 BuildNumber: 0

SortGraphNodes: Start of SortGraphNodes()

X i = 2 j = 1 value = 1372 Graph Node = (\UpdateBin\Packages\CommonNonEA.cab.pkg)

Output matrix:
-1 -1 -1
-1 -1 1372
-1 -1 -1

pred[0] = 0

pred[1] = -100

pred[2] = -1
BuildPaths: Calling CreatePaths()

dist[0] = 2147483647

dist[1] = 0

dist[2] = 2147483647

pred[0] = 0

pred[1] = -100

pred[2] = 1

Searching for Shortest Path weight from Node with index 1

Parent of 2 = 1

Parent of 1 = -100

Shortest Path weight from Node with Index 1 is 1372

List of nodes for this path = 1,
List of nodes for this path = 0,
Path: 01979D30
Target: Major: 5 Minor: 2 QFELevel: 5082 BuildNumber: 21869
Target: Major: 5 Minor: 2 QFELevel: 5082 BuildNumber: 21870

Processing Graph for GUID =	{7BB5F499-6B7F-4EE0-BCB9-A89AE3FC3E2C}
using path 01979D30 with weight 1372
Path: 01979D30
Target: Major: 5 Minor: 2 QFELevel: 5082 BuildNumber: 21869
Target: Major: 5 Minor: 2 QFELevel: 5082 BuildNumber: 21870
VerifySignatures: WARNING: Signature validation failed for following node. Trimming Edge from node index 1 .
Name of the Package is: \UpdateBin\Packages\CommonNonEA.cab.pkg
This package has following FROM and TO versions
FROM Version	Major: 0 Minor: 0 QFELevel: 0 BuildNumber: 0
TO Version	Major: 5 Minor: 2 QFELevel: 5082 BuildNumber: 21870
VerifySignatures failed for graph with base name of\IMGFS\7bb5f499-6b7f-4ee0-bcb9-a89ae3fc3e2c.dsm
Trying to find another path.

Deleting edge from node index: 2

dist[0] = 2147483647

dist[1] = 0

dist[2] = 2147483647

pred[0] = 0

pred[1] = -100

pred[2] = -1

Searching for Shortest Path weight from Node with index 1

Parent of 2 = -1

Shortest Path weight from Node with Index 1 is 0

Parent of 1 = -100

Shortest Path weight from Node with Index 0 is 0
No Valid paths were found for graph with base name of\IMGFS\7bb5f499-6b7f-4ee0-bcb9-a89ae3fc3e2c.dsm

BuildReturnValues: Returning HRESULT 0x80180015
LogValidatorReturnValues: Starts
UpdateOrderFromFileList failed with code 0x80180015

LogValidatorReturnValues: Bad Pacakge number: 1

Package with following GUID failed for reason 0x80180008: name \UpdateBin\Packages\CommonNonEA.cab.pkg
GUID =	{7BB5F499-6B7F-4EE0-BCB9-A89AE3FC3E2C}

LogValidatorReturnValues: Total number of Bad Packages: 1
Process Failed with code 0x80180015

UpdateOrderFromFileList: Returning HRESULT 0x80180015
+CPkgGraph::DeleteGraphs
-CPkgGraph::DeleteGraphs
UpdateValidator finished at 11:22:54 01/05/2010

Also, the kicthen I set up dumped the ROM, added my custom defaultcerts.dat and then rebuilt the ROM. I used the conservative flag but still doesn't work.

Not quite sure why this is. I can also upload the two scripts+files if wanted.