Did you try something simple like correlation?
(EDIT). The idea behind correlation is to use a template (in your case a trained road sign sample), and compare it to every position in the test image. The comparison operation I've used to generate the images below is called normalized cross-correlation. Roughly speaking, you standardize (mean=0, standard deviation=1) the pixels in the template and the image part you want to match, multiply them pixel by pixel, and calculate the mean value of the products. This way you get a "match score", i.e. a measure of similarity between the template and the test image at every position in the test image. The position with the best match (highest correlation) is the most probably candidate for the position of the road sign. (Actually, I've used the Mathematica function CorrelationDistance to generate the image below, which is 1 - (normalized correlation). So the darkest spot in the match image corresponds to the best match).
I don't have any other templates, so I simple cropped the sign from the second picture you posted:
Even though the template is rotated slightly, cross correlation still looks usable
and the best match is found at the right position:
(You'd need multiple scaled versions of each template to detect signs at any size, of course)