STAT RAISING PROBLEM I've sometimes had trouble Raising some of my ..

Question for Pokemon Black 2

STAT RAISING PROBLEM

I've sometimes had trouble Raising some of my Pokemons' Base Stats using Medicines in all my Pokemon Games.

Ex:
ZOROARK Lv. 68(PKRS)
HP: 168
Atk: 199
Def: 93
Sp. Atk: 194
Sp. Def: 87
Spd: 194

I've tried using Medicines to Raise his Defense and Special Defense Stats, but I keep getting: "It Won't have any Affect".

I've tried equipping the Macho Brace to Double the Effort Values earned, and Fighting Enemy Pokemon that give off "Defense" and "Special Defense" EV's but every time ZOROARK gains a Level, His "Def." and "Sp. Def." Stats only increase by 1 Point every time he Gains a Level.

Any advice on How to Raise Low Base Stats?
Do Natures and/or Characteristics help/determine this?

NOTE: this refers to All Pokemon. Zoroark was just an Example.

Please help if you can. Thanks!