If I understand correctly, you're trying to to get it to find the opening brace even on the next line. If you're complaining that it doesn't find the closing brace unless the whole thing is one line, I don't know why that wouldn't be working.
In any case, if you want % to have superpowers, the matchit plugin is the place to start. It's included in the normal distribution, so you shouldn't have to download it. Just add
:runtime macros/matchit.vim
To your .vimrc, and % will also know lots of new tricks (how to match balaced XML tags if/then/end if statements in languages that do those with keywords), etc. It won't solve your request directly, since matchit uses the same limitations as normal % (it wasnts the match to start at or after the cursor, on the same line). But since it can use regex searches as match markers (instead of just characters), it should be possible to configure it so the open expression is .\n.{ or some such that would meet that criteria, yet pick up a brace on a line further down.