you can try twisting the pressure release valve and make sure it's screwed in all the way
keg lube may help the seal better or you can try the thicker keg gaskets from williams brewing
http://www.williamsbrewing.com/KEG-LID-SEALING-O-RING-P58.aspx
i don't even need to seal with kegs with 30psi anymore with these rings
a lot of kegs need to be sealed with 30psi or so to really secure the lid, esp if they have any deformities etc. if the relief valve is leaking it may not be letting you get a good seal under pressure