I'd also definitely take a look at some of the png optimizers. They work by tweaking the parameters of the compression so it's a lossless operation (some of them will do some depth reduction in a lossless way if possible, but that doesn't always bring in better compression). Photoshop has been somewhat well known for not always producing an optimized png.