I have been searching for a solution to this situation for a long time. Searched and searched with no luck on the net. I guess that not many people is using the UVAtlas functionality that comes with DirectX9. So, these are my findings:
Partition and Pack always fail?
If you are using the Managed version of DirectX, the Partition and Pack methods will ALWAYS fail. I´m not sure if it´s related to the MDX implementation itself or (as ZMan suggested), may be due to MDX being based on an old version of DirectX. However, if you want to use them, you will have to deal with the native version: D3DXUVAtlasPartition and D3DXUVAtlasPack.
If you have been experiencing random failures in the UVAtlas generation, keep reading:
I have found that the problem is related to the MaxStretch parameter. If you don´t care much about stretching your geometry in the Atlas, the reasonable value is "1" (any amount of stretch allowed), but this value will cause errors with some meshes. I still wasn´t able to detect why and when it fails exactly.
More precisely, what happens then is that Partition method returns wrong values as output texture coordinates, even when returning S_OK as result. If you don´t detect this situation (as D3DXUVAtlasCreate doesn´t) and pass the resulting wrong mesh to the Pack method, it will throw an exception. The worst thing is that this exception is sometimes a native memory violation exception, so a managed try-catch won´t handle it and will force your application to exit.
To detect wrong texture information, Lock the mesh VertexBuffer (to get into its contents) and check for wrong resulting U,V values: +/- infinity, NaN, or extremely big values.
The general criteria to fix this situations is to low MaxStretch down. Most of the times (if not always), using 0.999f instead of 1 makes it, but maybe sometimes you will have to make it even lower, depending on your meshes.
Hope this helps.